[그래프이론 (Graph Theory) 문제풀이] For each n ∈ N, find an n-vertex graph such that κ′(G) > κ(G).

그래프이론 (Graph Theory) 문제를 풀어보자. 이번에 풀어볼 문제는 “For each n ∈ N, find an n-vertex graph such that κ′(G) > κ(G).” 이다.

Contents

그래프이론 (Graph Theory) 문제풀이

이번에 풀고자 하는 그래프이론 (Graph Theory) 문제는 아래와 같다.

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

(풀이) $n(G)=n$ 이라 하자.
내가 실제로 풀어보니 $n\leq 4$ 일 때는 $\kappa^\prime(G) = \kappa(G)$ 이 나올 수 밖에 없다.
그러면 이제 $n \geq 5$ 라고 가정하자.
아래와 같은 그래프 $G$ 를 생각해보자.

이 그래프의 구성요소로는 왼쪽에 삼각형이고 오른쪽은 $K_{n-2}$ 이 있다. 이 삼각형과 $K_{n-2}$ 가 한점을 공유하고 있다.
공유하고 있는 한점을 떼어 내면 disconnected가 되므로 $\kappa(G) = 1$ 이다.
삼각형의 엣지중 삼각형과 $K_{n-2}$ 이 공유하고 있는 한 vertex에 incident 한 두개의 edge를 떼어내면 disconnected 가 된다. 따라서 $\kappa^\prime(G) =2$
따라서 위의 그림처럼 그래프를 정의한다면 $\kappa(G) = 1 < \kappa^\prime(G) =2$ 이다.

참고글

[그래프이론 (Graph Theory)] For each even n ≥ 16, construct a 3-regular simple graph with n vertices having no 1-factor.

[그래프이론(Graph Theory) 문제풀이] Let G be a simple graph with diameter at least 4. Prove that complement of G has diameter at most 2.

[그래프이론(Graph Theory) 문제풀이] For each k, list the isomorphism classes of trees with maximum degree k and at most six vertices. Do the same for diameter k. (Explain why there are no others.)

문제출처- 광주과학기술원 최정옥 교수님의 “그래프 이론” 수업 (2023년 가을학기) 중 Homework 6 문제