그래프이론(Graph Theory)문제풀이하겠습니다. 이번 문제는 “For each k > 1, construct a k-regular simple graph having no 1-factor.” 입니다.
그래프이론(Graph Theory)문제풀이
이번에 풀어볼 문제는 아래와 같습니다.
For each k > 1, construct a k-regular simple graph having no 1-factor.
풀이) k=2 이면 삼각형을 생각해보자.
k가 짝수라면 K_k 를 생각하자. vertex갯수가 홀수개이므로 1-factor 존재안한다.
이제 k>2인 홀수라고 가정하자. 이제부터 k-regular simple graph 를 하나 잘 만들어 보겠다.
v 를 vertex라 하자.
v 와 adjacent 한 vertex v_1,v_2,...,v_{k-1} 를 줍시다.
매 i =1,2,...,k-1 마다 v_i 에 adjacent 한 k-1 개의 vertices v_{i,l}, l=1,2,...,k-1 를 만듭시다. 이제 각각의 i마다 v_{i,l}, w_{i,m} 가 \text{ for all } l,m 마다 adjacent 하도록 w_{i,m}, m=1,2,...,k-1 를 만듭시다. 이 때 w_{i,m} 은 총 짝수개 (k-1개) 니까 w_{i,2n-1} 과 w_{i,2n}를 이어서 edge를 추가시키면 k-regular graph G 가 만들어집니다.
이제 1-factor를 만들기 위하여 i=1,2,...,k-1 중 edge vv_i 를 선택해야 합니다. 만약에 vv_2 를 1-factor를 만들기 위한 edge로 선택했다고 합시다. 그러면 이제 G[v_1,v_{1,1},v_{1,2},...,v_{1,k-1},w_{1,1}, ...w_{1,k-1}] 의 1-factor를 찾아야 하는데요. G[v_1,v_{1,1},v_{1,2},...,v_{1,k-1},w_{1,1}, ...w_{1,k-1}] 의 vertex 갯수는 홀수개이므로 G[v_1,v_{1,1},v_{1,2},...,v_{1,k-1},w_{1,1}, ...w_{1,k-1}] 의 1-factor는 존재하지 않습니다. 따라서 G 의 1-factor는 존재하지 않습니다.
문제출처- 광주과학기술원 최정옥 교수님의 “그래프 이론” 수업 (2023년 가을학기) 중 Homework 5 문제