Bipartite graph has a vertex with all incident edges in some perfect matching

Question

Let $G$ be a bipartite graph with a perfect matching. Prove that $G$ has a node $v$ for which every edge incident to $v$ belongs to a perfect matching.

I don't think that this question is true if all the edges incident to $v$ belongs to the same perfect matching.

My attempt: Suppose $v$ is not incident to any perfect matching of $G$. This implies that $G$ cannot have a perfect matching, which is a contradiction.

Am I on the right way, thanks for your comment.

Answer 1

I believed that the answer has been explained sufficiently by a previous post.

I will however expand on the explanation on some of the steps since there appears to still be some confusion.

Let $G=(U,V,E)$ be the bipartite graph, with $U$ and $V$ being the two partitions in the bipartite graph, and $E$ the edges. By supposition, a perfect matching exist in the graph.

• 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 neighbour of $u_0$ in $M$ (i.e. $u_0v_1\in M$).
• Now pick an edge of $\{v_1,u_1\}$ that does not belong to $M$. If this does not exist, this meant that $v_1$ has all its incident edges in a perfect matching and you are done.
• Therefore, you can 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, which means the complement of the cycle (containing $\{v_0,u_0\}$), combined with the unused edges in $M$ is also a perfect matching and you are done.