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.
Let $M$ be a maximum matching. Any vertex cover must contain at least one vertex out of each edge in the matching. Hence the size of a minimum vertex cover equals the size of the maximum matching if there's a vertex cover consisting of one vertex out of each edge of $M$.
Denote the edges of $M$ by $e_1 = (x_1,y_1),\ldots,e_m = (x_m,y_m)$, where $m = |M|$. Let $v_i$ be a Boolean variable which determines which of $x_i,y_i$ we pick. We can express the constraint that an edge not in $M$ is covered as a disjunction of two literals. Hence we can express the existence of a vertex cover of size $M$ as a 2CNF. Since 2SAT is solvable in polynomial time, we can determine whether such a vertex cover exists.
