For each k > 1, construct a k-regular simple graph having no 1-factor.

문제출처

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

Solution

아래 풀이엔 논리적 오류는 없으나, 아래에 그려둔 k=3, k=5 예시에 K4를 추가하는 방식으로 그래프를 구성해보면 더 쉽게 표현할 수 있다. 규칙성을 찾아보고 예시의 두 그래프를 각각 G1, G2로 정의하고, Union 기호를 이용해 K4를 몇개 추가하면 조건을 완성시킬 수 있을지 검토해보면된다. 

 

 

We will consider two cases:

---

1. Case 1: $k$ is even
   • Imagine the complete graph $K_{k+1}$.
     • This is a $k$-regular graph with $k+1$ vertices.
     • Since $K_{k+1}$ has an odd number of vertices, it is impossible to pair up all vertices. Therefore, one vertex will always remain unmatched.
   • As a result, $K_{k+1}$ is a $k$-regular graph that has no 1-factor.

---

2. Case 2: $k$ is odd
   • We will construct a graph with a central vertex $v^*$, connecting it to $k$ subgraphs to create a $k$-regular graph.
   Construction:
   • Let each subgraph $G_i$ $(1 \leq i \leq k)$ connected to the vertex $v^*$ have an odd number of vertices.
   • These subgraphs are independent of each other, and the only connection between them occurs through the central vertex $v^*$.
   • To ensure the regularity of the graph, each subgraph $G_i$ will contain $(k-1) \times 2 + 1$ vertices.
     • One vertex in $G_i$ will have degree $k-1$, and all other vertices will have degree $k$.
     • The $k-1$ degree vertex in $G_i$ is adjacent to $v^*$ in the entire graph.
   Examples:
   • For $k=3$, $G_i$ will have 5 vertices.
   • For $k=5$, $G_i$ will have 9 vertices.
   • Below is an example for $k=3$ and $k=5$:

 

2. Mathematical Induction:
   • We will prove that this construction works for all odd $k$ using mathematical induction:
     1. Base Case:
        • Let $k=3$. We construct a subgraph $G_i$ with 5 vertices:
          • One vertex has degree $k-1=2$, while the other vertices have degree $k=3$.
          • This satisfies the conditions of the problem.
     2. Inductive Hypothesis:
        • Assume that for $k=n$, a subgraph $G_i$ exists with $(n-1) \times 2 + 1$ vertices, where:
          • One vertex has degree $n-1$, and the remaining vertices have degree $n$.
     3. Inductive Step:
        • For $k=n+2$, we construct the subgraph by adding four vertices $a, b, c, d$ to $G_i$:
          • Add edges as follows:
            1. Connect $a$ and $x$, as well as $a$ to vertices in a subset $A$ of $V(G_i) \setminus {x}$.
            2. Similarly, connect $b$ and $x$, as well as $b$ to vertices in $A$.
            3. Connect $c$ and $d$ to vertices in a disjoint subset $B$.
            4. Add edges $a-c$, $b-c$, $a-d$, $b-d$, and $c-d$.
        • This ensures that all vertices maintain degree $n+2$ and preserves the properties of the graph.
   Properties of the Constructed Graph:
   • Since each subgraph $G_i$ has an odd number of vertices, it cannot form a 1-factor on its own.
   • When $v^*$ is removed, the remaining subgraphs still have an odd number of vertices, making a 1-factor impossible.
   Using Tutte's Theorem:
   • According to Tutte's theorem, a graph $G$ has a 1-factor if and only if for every vertex set $S \subseteq V(G)$, the number of odd components in the graph $o(G-S)$ satisfies:
     $$
     o(G-S) \leq |S|,
     $$
     where $o(G-S)$ is the number of odd components in the graph obtained by removing the vertex set $S$.
   Violation of Tutte's Theorem:
   • When $v^*$ is removed, the remaining components are the $k$ subgraphs $G_1, G_2, \dots, G_k$.
   • Let $S = {v^*}$, the single vertex we removed.
   • The number of odd components in the graph after removing $S$ is $k$, which is greater than $|S|$ ($|S|=1$).
   • By Tutte's theorem, this violates the necessary condition.

 

 

Conclusion:
Thus, for $k$ odd, we can construct a $k$-regular graph with no 1-factor.