0
$\begingroup$

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

  • 0
    A triangle ($K_3$) is 2-edge connected, right? But with an odd number of vertices, can it have a perfect matching?2012-07-08

1 Answers 1

3

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.