# In every bipartite graph G, there exists a vertex v such that v is matched in every maximum matching

As a part of König's Theorem proof I have to prove following lemma:

In every bipartite graph G, there exists a vertex v such that v is matched in every maximum matching.

Any help?

• I find your question hard to understand. Could you reformulate it (e.g. for every bipartite graph $G$, there exists vertex cover $C \subset G$ such that...)? – dtldarek Aug 22 '13 at 7:45
• Do you mean that in every bipartite graph $G,$ there exists a vertex $v$ such that $v$ is matched in every maximum matching? – Will Orrick Aug 22 '13 at 17:49
• @WillOrrick Yes, exactly. – alop789312 Aug 23 '13 at 21:48

This answer is not very direct (in that it uses other results) so I'm not sure how useful it will be to you.

By a theorem of Gallai's, a graph is factor critical if it is connected and for every vertex $v$, there exists a vertex which misses $v$.

Theorem (Gallai): Let $G(V,E)$ be a connected graph. $G$ is factor critical if for every vertex $v\in V$, there exists a maximum matching which misses $v$.

Proof: We shall prove that if $G$ is a graph such that for every vertex $v\in V$, there exists a maximum matching which misses $v$, then every maximum matching of $G$ misses exactly one vertex, i.e. each maximum matching is a near-perfect matching.

Suppose for the sake of contradiction that there exists a maximum matching which misses two (or more) vertices of $G$. It follows that every maximum matching misses two (or more vertices). Let $M$ be the maximum matching with missed vertices $u$ and $v$ separated by the smallest distance over all other matchings. Then $u$ and $v$ cannot be adjacent since otherwise we may add edge $(u,v)$ to $M$.

Let $w$ be an intermediate vertex on the shortest $uv$-path. Let $N$ be the matching which misses $w$ such that $|N\cap M|$ is maximal. $N$ cannot miss $u$ or $v$ since otherwise, $wu$ or $wv$ would be a shorter path between missed vertices, contradicting the minimality of $u$ and $v$ in $M$. It follows that $N$ must miss some vertex $x\neq w$ which is covered by $M$ (recall that they cover the same number of vertices). Let $y$ be the vertex such that $(x,y)\in M$. There must exist an edge $e$ adjacent to $y$ in $N$ for otherwise $x$ and $y$ would be adjacent free vertices in $N$. But then replacing $e$ with $(x,y)$ in $N$ produces a matching with $t$ free and larger intersection with $M$. This is a contradiction. $\square$

Now we can prove your result:

In every bipartite graph $G$, there exists a vertex $v$ that is matched in every maximum matching.

Proof: Suppose otherwise. Then every vertex in $G$ must be missed by a maximum matching. Working with the components of $G$, we may assume without loss of generality that it is connected. The previous theorem implies that the graph is factor critical. In particular, this means that the graph's two components, $A$ and $B$, have sizes $n$ and $n+1$ respectively (with maximum matching of size $n$). But then a maximum matching cannot possibly miss a vertex in $A$ for it must then miss two vertices in $B$. This contradicts the fact that the graph is factor critical. $\square$.

In passing, I mention that this result almost immediately implies König's theorem. Let $G$ be a minimal counter-example. Let $v$ be a vertex which is matched by every maximal matching of $G$. Then we must have $\nu(G\setminus v) < \nu(G)$ for otherwise there exists a maximal matching of $G\setminus v$ of size $\nu(G)$, i.e. a maximal matching of $G$ which misses $v$. By minimality of $G$, it follows that $\tau(G\setminus v) = \nu(G\setminus v) < \nu(G)$. Adding back $v$ to a minimal cover of $G\setminus v$ then gives $\tau(G) \le \nu(G)$ as required.