1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ thank you sir. but the question is so much simpler than that ! the graph is undirected and i know nothing about strongly connected components ! $\endgroup$ – Arman Malekzadeh Apr 7 '16 at 18:41
  • $\begingroup$ @ArmanMalekzade I could not know that, because you provided no context to the question. I would advise you to add it, otherwise the people that could answer your question have very limited knowledge of what would actually help you. Context is very important, consider this when asking your future questions! $\endgroup$ – dtldarek Apr 7 '16 at 18:51

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.