Does $\beta(G)=\alpha'(G)$ always?

671 Views Asked by At

Does there exist a graph where the minimum vertex cover does not equal the size of the maximum matching?

I'm thinking that if it does, then it cannot be a bipartite graph and so it contains an odd cycle.

1

There are 1 best solutions below

0
On

If graph is bipartite, the assertion is konig theorem, nevertheless the assertion is not generally true; counterexample is K3.