Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Seems to be an easy question, but I can't find the right direction.

Let $G$ connected graph on at least 4 vertices, such that every edge in it, participates in a perfect matching. Prove that $G$ is 2-connected.

Any help will be appreciated.

Thanks in advance.

share|improve this question

2 Answers 2

up vote 2 down vote accepted

Gerry Myerson has shown that $G$ must be $2$-edge-connected. Since you didn’t specify which you meant, I’ll show that $G$ must be $2$-vertex-connected.

Suppose that $G$ is not $2$-vertex-connected. Then there is a vertex $v$ whose removal disconnects $G$ into components $C_1,\dots,C_n$ for some $n\ge 2$. Fix $k\in\{1,\dots,n\}$, let $e$ be an edge from $v$ to $C_k$, and consider a perfect matching $M$ that includes $e$. $M$ cannot include any other edge incident at $v$, so the other edges of $M$ must lie in the components $C_1,\dots,C_n$. Thus, each of these components except $C_k$ must have an even number of vertices, and $C_k$ must have an odd number of vertices. Now choose $i\in\{1,\dots,n\}\setminus\{k\}$; the same argument shows that $C_k$ must have an even number and $C_i$ an odd number of vertices. This contradiction shows that $G$ must be $2$-vertex-connected.

share|improve this answer
    
I indeed meant vertex connectedness. Interesting approach. Thank you. –  Pavel Aug 20 '12 at 8:05

If $G$ has a perfect matching, it has an even number of vertices. Suppose there's an edge $e$ whose removal disconnects $G$. Removing that edge splits $G$ into two pieces. Either each piece has an even number of vertices, or each piece has an odd number of vertices.

If each piece has en even number of vertices, then $e$ can't be part of a matching, since the other edges in the matching must each be wholly in one of the two pieces, so you must get a matching on each of the pieces, but once you've used $e$ each piece has an odd number of veertices.

If each piece has an odd number of vertices, then $e$ must be a part of every matching, and you can't use any edge that meets $e$ at a vertex. For if you use such an edge, that leaves an odd number of vertices in the piece containing that edge, and there's no matching there.

share|improve this answer
    
Although I meant vertex connectedness, it gives another perspective. Thanks. –  Pavel Aug 20 '12 at 8:06

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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