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.
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.
If graph is bipartite, the assertion is konig theorem, nevertheless the assertion is not generally true; counterexample is K3.