4
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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...)? $\endgroup$ – dtldarek Aug 22 '13 at 7:45
  • $\begingroup$ Do you mean that in every bipartite graph $G,$ there exists a vertex $v$ such that $v$ is matched in every maximum matching? $\endgroup$ – Will Orrick Aug 22 '13 at 17:49
  • $\begingroup$ @WillOrrick Yes, exactly. $\endgroup$ – alop789312 Aug 23 '13 at 21:48
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.