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

그래프이론(Graph Theory) 문제풀이 하겠습니다. 이번에 풀어볼 문제는 “For each even n ≥ 16, construct a 3-regular simple graph with n vertices having no 1-factor.” 입니다.

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

For each even n ≥ 16, construct a 3-regular simple graph with n vertices having no 1-factor.

풀이)

우선은 n=16이고 1-factor가 없는 3-regular simple graph 를 아래와 같이 만들 수 있다.

이제 vertex를 두개씩 추가해서 vertex 갯수 n=18,20,22… 인 simple graph 만들것이다. vertex를 추가하는 방법에 대해서는 아래 그림에 표현하였다.

위의 그림처럼 한다면 기존 vertex의 degree를 건들이지 않고 degree가 3인 두개의 vertex를 추가할 수 있다. 이 방법을 그림1.에 적용하여 아래와 같이 n이 16이상인 짝수일 때 3-regular graph 를 만들 수 있다.

위의 그림3.의 그래프에서 1-factor를 만들기 위해서 edge e1,e2,e3중에 e2를 택했다고 하자. 그러면 이제 G1의 1-factor를 찾아야 겠는데! G1의 vertex갯수는 홀수개이므로 G1의 1-factor를 존재하지 않는다. 따라서 graph에서 1-factor가 존재하지 않는다.

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