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.

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

share|improve this question
    
A triangle ($K_3$) is 2-edge connected, right? But with an odd number of vertices, can it have a perfect matching? –  Gerry Myerson Jul 8 '12 at 7:05
add comment

1 Answer 1

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.

share|improve this answer
add comment

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.