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}$가 한점을 공유해 만들어지는 그래프를 구성했다.