🛠️ Steven Gong

Search

SearchSearch

Jul 26, 2023, 1 min read

Graph Matching

Konig’s Theorem

First understand what Alternating Paths and Augmenting Paths are.

Konig’s Theorem

In a Bipartite Graph, the size of a maximum matching is equal to the size of a minimum cover.

This is proven using an algorithm which looks for augmenting paths called the Bipartite Matching Algorithm.

Graph View

Backlinks

  • Bipartite Matching Algorithm
  • Graph Matching
  • MATH 239 - Introduction to Combinatorics

Created with Quartz, © 2025

  • Blog
  • LinkedIn
  • Twitter
  • GitHub