For each n ∈ N, find an n-vertex graph such that $κ′(G) > κ(G)$.

문제출처

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

---

Solution

1. If the graph is initially disconnected,  $\kappa'(G) = 0$ . Thus, $\kappa(G) = \kappa'(G) = 0$. Therefore, we will only consider connected graphs.

2. For , n = 1 :

• $ \kappa(G) = \kappa'(G) = 0 $ is trivial.

3. For , n = 2 :

• The path graph ,$P_2$  is the only connected graph, and  $\kappa(G) = \kappa'(G) = 1$ is trivial.

4. For , n = 3 :

• The triangle graph $C_3$ is the only connected graph, and $\kappa(G) = \kappa'(G) = 2$ is trivial.

5. For , n = 4:

• There are two cases:
  • The cycle $ C_4$:
    $ \kappa(G) = \kappa'(G) = 2 $ is trivial.
  • A graph where a $C_3$ and a $P_2 $ share one vertex \(denoted as Assemble\($C_3, P_2 $ \)\):
    • $\kappa(G) = 1 $by choosing the common vertex.
    • $ \kappa'(G) = 1 $ by choosing the edge of $P_2$ that is incident to the common vertex.

6. There is no $ n $-vertex graph such that $ \kappa'(G) > \kappa(G) $ for $ n \leq 4 $.

7. For, $ n \geq 5 $:

• Consider Assemble\( $C_{n-2}, C_3$ \), where $ C_{n-2} $ and $ C_3 $ share a common vertex:
  • $ \kappa(G) = 1 $ by choosing the common vertex of $C_{n-2} $ and $ C_3 $.
  • $\kappa'(G) = 2 $ by choosing the edges of $C_3$ that are incident to the common vertex.
  • Thus, $ \kappa'(G) > \kappa(G)$.

이 경우, n=1,2,3,4에 대해선 존재하지 않는다. 이를 증명하기 위해선 n에 대한 모든 가능한 그래프를 그리고, 조건에 만족하지 않음을 보여야한다. 이후 n>4에 대해서 특정 형태의 그래프가 항상 가능함을 보이고, 그 형태의 그래프에선 조건이 만족됨을 보였다. 필자의 경우엔 $C_3$와 $C_{n-2}$가 한점을 공유해 만들어지는 그래프를 구성했다.