1 / 8 Flows, Matchings & Graph Structure Beyond Dinic

Konig Stops At Bipartite

Konig's theorem and its corollaries. More than one holds; select every statement that is true for bipartite graphs.

A

Minimum path cover of a DAG reduces to maximum matching on a split bipartite graph.

B

Maximum matching needs the blossom algorithm, since a bipartite graph can still contain odd cycles.

C

Minimum vertex cover size equals maximum matching size.

D

Maximum independent set size equals ∣V∣|V| minus the maximum matching size.

E

Minimum vertex cover is NP-hard here too, so the matching only gives a lower bound.