그래프이론 (Graph Theory) 문제를 풀어보자. 이번에 풀어볼 문제는 “Use Menger’s Theorem to prove that κ(G) = κ′(G) for every 3-regular graph G.” 이다.
그래프이론 (Graph Theory) 문제풀이
이번에 풀고자 하는 그래프이론 (Graph Theory) 문제는 아래와 같다.
Use Menger’s Theorem to prove that κ(G) = κ′(G) for every 3-regular graph G.
이제 이 문제를 풀어보려고한다. G 는 3-regular graph 이므로 \delta(G)=3 이고 \kappa(G) \leq \kappa^\prime(G) \leq \delta(G)=3 입니다.
\kappa(G)=0 인 경우
이 때 \kappa(G)=0 이면 G 는 disconnected 이므로 \kappa^\prime(G)=0 입니다.
\kappa(G)=3 인 경우
\kappa(G)=3 이면 \kappa(G) \leq \kappa^\prime(G) \leq \delta(G)=3 이므로 \kappa^\prime(G) = \kappa(G) = 3 입니다.
이제 1 \leq \kappa(G) \leq 2 라고 합시다.
S 를 |S| = \kappa(G) 를 만족하는 vertex cut 이라고 합시다.
\kappa(x,y) = \kappa(G) 인 x,y를 생각합시다.
그리고 H_1 , H_2 를 G-S의 두개의 component인데 x \in H_1 이고 x \in H_2 라고 합시다.
v \in S마다 v 는 H_1, H_2 에 동시에 neighbor를 갖습니다.
그리고 \kappa(x,y) = \kappa(G) 인 x \in H_1 과 x \in H_2 가 존재합니다.
Menger’s theorem 에 의하여 \kappa(x,y) = \lambda(x,y)=\kappa(G) 입니다.
internally dijoint xy -path 는 S 위에 있는 vertex 를 무조건 지납니다.
그리고 S 위의 vertex에 대하여 이 vertex를 지난 xy-path 는 무조건 존재합니다.
\kappa(G)=1 인 경우
먼저 \kappa(G) =1 인 경우에 대해 생각해보자.
이 때는 S = \{ v_1 \} 입니다.
v_1 는 H_1, H_2 에 동시에 neighbor hood를 갖는다.
이 때 H_1, H_2 중에 하나의 component에는 하나의 edge로만 연결되어있을 것이다.
왜냐하면 3-regular graph니까!
하나의 edge로만 연결되어있는 edge만 끊어버리면 disconnected가 되므로 \kappa(G) = \kappa^\prime(G) =1 이다.
\kappa(G)=2 인 경우
S = \{ v_1, v_2 \} 라 하자.
v_1, v_2 가 adjacent 한 경우
이 경우에는 아래와 같은 경우이다. 여기서 e_5, e_6를 끊어버리면 disconnected가 되므로 \kappa^\prime(G)=\kappa(G)=2 이다.
v_1, v_2 가 adjacent 하지 않는 경우
이 경우에는 각각의 v_i 는 H_1, H_2 둘중 한곳에만 하나의 edge로만 연결되어있을 테다.
v_i 마다 하나의 neighbor만 갖는 H_j 와 연결된 edge들을 제거하면 disconnected가 된다. 따라서 \kappa^\prime(G) = \kappa(G) =2
[그래프이론 (Graph Theory) 문제풀이] Determine κ and κ′ for each graph below.
[그래프이론 (Graph Theory) 문제풀이] For each n ∈ N, find an n-vertex graph such that κ′(G) > κ(G).
문제출처- 광주과학기술원 최정옥 교수님의 “그래프 이론” 수업 (2023년 가을학기) 중 Homework 6 문제