I'm preparing for exam and I came across this problem:
We say that a graph is König's graph when the sizes of its minimum vertex cover and maximum matching are equal. Find a polynomial time algorithm deciding if a graph is König's graph.
I'm stuck. I know that in bipartite graphs this always holds. I also know that we can find maximum matching in every graph in polynomial time. But I don't know how to connect this with minimum vertex cover problem which in general is NP-complete.