Suppose $G$ is a graph where every vertex has degree $3$. There is no single edge which separates the graph. My question is, must $G$ necessarily have a perfect matching? I tried drawing some graphs which satisfies the conditions, and I always got a perfect matching…
[Math] Graph where every vertex has degree 3, perfect matching
combinatoricsgraph theory
Best Answer
Yes, your hypothesis is correct, it is sufficient to prove it for connected graphs.
Given $U$ a set of vertices consider $G-U$. Given a connected component $K$ in $G-U$ count the number of edges in $G$ that had a vertex in $K$. If this number is $0$ that is because $K=G-U$ (notice that $K$ would also be connected in $G$, and would not have any edges coming out from it). If this number is $1$ then this means there is a unique edge in $G$ coming out from $K$, this edge would be a bridge of $G$, which does not exist by hypothesis. If this number is $2$ there are two options, there is a vertex $u$ of $K$ that is adjacent to both vertices, in which case the edge connecting $u$ with the rest of $K$ is a bridge, or the second option is that the two edges come out of different vertices of $K$, in this case $K$ would have $2$ vertices of degree $2$, and the rest would be of odd degree, meaning $K$ has an even number of vertices.
What have we concluded? if $G-U$ is not connected then every connected component of $G-U$ with an odd number of vertices has at least $3$ edges going to $U$.
This means if there are $d$ connected components with an odd number of vertices then there are at least $3d$ edges going from $U$ to $G-U$. On the other hand the number of edges going from $U$ to $G-U$ is at most $3|U|$. Let $E$ be the number of edges between $U$ and $G-U$, then we have:
Thus $3d\leq E\leq3|U|\implies d\leq |U|$.
In other words if we remove $k$ vertices from $G$ we have at most $k$ connected components with an odd number of vertices, so by Tutte's theorem there is a perfect matching.