# Match covered graph is 2-connected

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.

-

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.

-
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.

-
Although I meant vertex connectedness, it gives another perspective. Thanks. –  Pavel Aug 20 '12 at 8:06