For each even n ≥ 16, construct a 3-regular simple graph with n vertices having no 1-factor.

문제출처

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

---

Solution

아래 풀이는 일반화된 풀이라기엔 부족한 감이 있다. 필자는 연결그래프만을 상상했기에 이런 풀이를 작성했으나, n=16, n=18 케이스에 K4를 추가해가는식으로 그래프를 구성하면 일반화된 풀이를 구성할 수 있다.

 

굳이 이렇게 연결그래프일 필요없다.

• The above figure shows a 3-regular graph (( n = 16 )) having no 1-factor, as demonstrated in Problem 5 using Tutte's theorem.
• Using the same definitions of ( v^* ) and ( G_i ) from Problem 5, let the subgraphs on the far left, center, and far right in each graph be ( G_1 ), ( G_2 ), and ( G_3 ), respectively.
• We can expand ( G_3 ) by adding two vertices while maintaining the 3-regular property.

---

Check Tutte's Theorem:

1. Odd Components After Removing ( v^* ):
   • When ( v^* ) is removed, the remaining components are still ( G_1 ), ( G_2 ), and ( G_3 ).
   • Each subgraph still contains an odd number of vertices, so the number of odd components remains 3.
2. Set ( S = {v^*} ):
   • After removing ( S ), we have:
     $$
     o(G-S) = 3 \quad \text{and} \quad |S| = 1.
     $$
   • This violates the condition ( o(G-S) \leq |S| ) required by Tutte's theorem.

---

Conclusion:
Thus, the 3-regular simple graphs constructed in this way for even ( n \geq 16 ) do not have a 1-factor.