Prove or disprove: If G is a 3-regular graph with at most two cut-edges, then G has a 1-factor.

문제출처

광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 8

---

Problem

Prove or disprove: If $G$ is a 3-regular graph with at most two cut-edges, then ( G ) has a 1-factor.

---

Solution

1. We will use Tutte's theorem and Proposition 4.1.12:
If $S$ is a set of vertices in a graph $G$, then:
$$|[S, \bar{S}]| = \sum\limits_{v \in S} d(v) - 2e(G[S]),$$
where $|[S, \bar{S}]|$ represents the number of edges between $S$ and $\bar{S}$, and $e(G[S])$ is the number of edges within $S$.

2. Since $G$ is a 3-regular graph:
$$|[S, \bar{S}]| = \sum\limits_{v \in S} d(v) - 2e(G[S]) = 3|S| - 2e(G[S]).$$

3. Each odd component of $G - S$ requires at least 3 edges to connect to $S$. Thus:
$$o(G - S) \leq \frac{|[S, \bar{S}]|}{3} = \frac{3|S| - 2e(G[S])}{3} = |S| - \frac{2e(G[S])}{3},$$
where $o(G - S)$ is the number of odd components in $G - S$.

4. Since $e(G[S])$, the total number of edges in $S$, satisfies $e(G[S]) \geq 0$, we have:
$$o(G - S) \leq |S| - \frac{2e(G[S])}{3} \leq |S|.$$

5. Therefore, Tutte's condition holds, and a 1-factor exists in $G$.