graph theory

Question

In a Bipartite graph,the size of the maximum matching is equal to the size of the minimum vertex cover ...can somebody prove this logically ?

Comments

It is know as König's theorem

https://en.wikipedia.org/wiki/K%C5%91nig%27s_theorem_(graph_theory)

Link above explain it logically.

Answer 1

Its is stated as number of edges in maximal matching is equal to minimum vertex cover. for bipartite graph only.

It is know as König's theorem

https://en.wikipedia.org/wiki/K%C5%91nig%27s_theorem_(graph_theory)

Visualize an 2 vertex complete graph which is also an bipartite graph no of edge in maximum matching is one (only one is possible) and minimum vertex cover is 1

Visualize an 3 vertex 2 edge bipartite graph its maximal matching and minimum vertex cover=2.

Base of proof is

No vertex in vertx cover can cover more then one edge of maximal matching.