Call a graph k-edge connected iff for every set $X$ of fewer than $k$ edges, $G|X$ is connected. Prove that every 2-edge connected graph has a perfect matching.

I would go about this starting with 3-edge connected graphs first. (Note that $k$-connected means the same thing but for sets $X$ of vertices. )

  • $\begingroup$ A triangle ($K_3$) is 2-edge connected, right? But with an odd number of vertices, can it have a perfect matching? $\endgroup$ Jul 8 '12 at 7:05

Theorem: For all $n \geq 5$, there exists a $2$-edge-connected graph on $n$ vertices that does not have a perfect matching.

Proof: Graphs with perfect matchings need an even number of vertices, so the theorem is trivially true for odd $n$.

Now assume $n$ is even and $n \geq 6$. Let $G=(V,E)$ be the graph defined by:

  • Vertex set $V=\{X,Y\} \cup \{1,2,\ldots,n-2\}$, and
  • Edge set $E=\{Xt:t \in \{1,2,\ldots,n-2\}\} \cup \{Yt:t \in \{1,2,\ldots,n-2\}\}$.

We can readily see that the graph is indeed $2$-edge-connected.

We next observe that every edge has either $X$ or $Y$ as an endpoint. Hence, if $G$ has a perfect matching, we must have that $|\{X,Y\}| \geq |\{1,2,\ldots,n-2\}|$, which is untrue since $n-2 \geq 4$. End Proof.

A 2-edge-connected graph with 6 vertices and no perfect matching Figure: a counter-example on $6$ vertices (drawn using Cytoscape).

This could alternatively be shown using Tutte's Theorem, which gives necessary and sufficient conditions for the existence of a perfect matching in a graph:

Tutte's Theorem: A graph $G=(V,E)$ has a perfect matching if and only if for every subset $U$ of $V$, the subgraph induced by $V \setminus U$ has at most $|U|$ connected components with an odd number of vertices.

Note: this construction also generalises to $k$-edge-connected, by replacing $\{X,Y\}$ with a set of size $k$. There will be some small exceptions, but for any fixed $k$, for all sufficiently large $n$ there will exist a $k$-edge-connected graph with no perfect matching.


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.