Let $G$ be a simple $3$-regular (every vertex has degree $3$) $2$-edge connected graph. Does $G$ contain a perfect matching?
$\begingroup$
$\endgroup$
3
-
7$\begingroup$ Yes. See Kristal Cantwell's answer below. My favourite proof of this result is to observe that the vector $(\frac{1}{3}, \frac{1}{3}, \dots, \frac{1}{3})$ is in the perfect matching polytope of $G$, and hence $G$ has at least one perfect matching. $\endgroup$– Tony HuynhCommented Jan 21, 2016 at 17:22
-
$\begingroup$ Thanks a lot. can you please send message, i am new here and i don't know how to make chat $\endgroup$– Adam jackCommented Jan 21, 2016 at 19:19
-
2$\begingroup$ This is a Q & A site, not a discussion board, and hence chat is not possible. In the case of the responses you've gotten, both respondents are using their real names and can be googled. E-mail them. $\endgroup$– Alexander WooCommented Jan 21, 2016 at 19:32
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
Every bridgeless cubic graph contains a perfect matching according to Petersen's Thereom.
answered Jan 21, 2016 at 16:38
-
$\begingroup$ Thanks bro .. how i can make chat with you ? $\endgroup$ Commented Jan 21, 2016 at 19:06
$\begingroup$
$\endgroup$
Just in case you have more questions of this type, there is a theorem of Tutte, which gives necessary/sufficient condition for a graph to have a perfect matching:
https://en.wikipedia.org/wiki/Tutte_theorem
Since you are forbidding cut edge (bridge), and since an odd component of G-U must send odd number of edges to U (hand shake lemma), each odd component of G-U must sent at least 3 edges to U, but G is cubic, so the condition of the theorem is satisfied.
