[Math] A bipartite graph with a perfect matching has a vertex with each edge contained in a perfect matching

bipartite-graphsgraph theory

A matching or independent edge set in a graph is a set of edges without common vertices.

A perfect matching (also called 1-factor) is a matching which matches all vertices of the graph.

a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint sets and (that is, and are each independent sets) such that every edge connects a vertex in to one in.

Now imagine a bipartite graph like G which has a perfect matching.
Prove that there exists a vertex in G like V such that every edge connected to G is in a perfect matching.

Note : I tried to prove it but i have nothing to start with ! Thanks in advance.

Edit : The graph is a simple undirected graph and i don't know anything about "strongly" connected graphs.

Best Answer

Hint:

  • Let $M$ be some perfect matching n $G = (U,V,E)$.
  • Denote by $\vec{G}$ the graph $G$ directed by $M$, that is, $$ \vec{E} = \{(u,v) \mid \{u,v\} \in E \cap M\} \cup \{(v,u) \mid \{u,v\} \in E \setminus M\}.$$
  • Set $C_1, C_2, \ldots$ to be the strongly connected components of $\vec{G}$.
  • These components have very special structure, in particular any edge that is contained within any oh those components belongs to some perfect matching.

Different hint:

(This is actually the very same solution, only the formulation is a bit simpler, however, not as nice.)

  • Let $M$ be some perfect matching.
  • Take any vertex $v \in V$. Set $v_0 = v$. Assume it has an edge $\{v_0,u_0\}$ that does not belong to any perfect matching (otherwise you are done), where $u_0$ is the other vertex incident to that edge.
  • Let $v_1$ be a neighbor of $u_0$ in $M$.
  • Repeat these steps to get a sequence $v_0,u_0,v_1,u_1,v_2,\ldots$ alternating between $V$ and $U$, and also edges between them alternating between $E \setminus M$ and $M$.
  • Because the graph is finite, you will find $v_i = v_j$ (or $u_i = u_j$) for some $i < j$, and let $i$ and $j$ be the first such pair.
  • Observe that you got an alternating cycle.

I hope this helps $\ddot\smile$

Related Question