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