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