Konig Stops At Bipartite

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

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

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

Minimum vertex cover size equals maximum matching size.

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

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