그래프이론(Grpah Theory)문제를 풀어보겠습니다. 오늘 마주할 문제는 아래에 나와있습니다.
Prove that the Petersen graph has no cycle of length 7.
Petersen graph 에는 길이가 7짜리 cycle이 존재하지 않는다는 얘기입니다. 오늘은 Petersen graph 에는 길이가 7짜리 cycle이 존재하지 않다는 사실을 보이겠습니다.
도움이 될만한 글:
- [그래프이론(Graph Theory) 문제풀이] Find all simple graphs with n vertices having no isolated vertex and no induced subgraph with exactly two edges.
- [그래프이론(Graph Theory) 문제풀이]Let P and Q be be paths of maximum length in a connected graph G. Prove that P and Q have a common vertex.
- [그래프이론 문제풀이] Let u and v be adjacent vertices in a simple graph G. Prove that uv belongs to at least d(u) + d(v) − n(G) triangles in G.
- [그래프 이론(Graph Theory)-1] k-set과 k-subset
그래프이론(Grpah Theory) 문제 풀이
오늘 풀어야 하는 문제를 다시 언급해 드리겠습니다. 풀어야 하는 문제는 아래와 같습니다.
Prove that the Petersen graph has no cycle of length 7.
이 문제는 어떻게 풀어야 할가요? 길이가 7인 cycle을 만들기 위해서는 길이가 6인 path 부터 만들어야 합니다. 길이가 6인 path 부터 만들어 보겠습니다. Petersen graph 의 vertex를 12,13,14,15,23,24,25,34,35,45 라고 표시합시다. 그리고 이제 길이가 6인 path를 만들겠습니다.
시작점
대칭성에 의해 시작점으로 아무 점이나 고르면 됩니다. 그러면 12를 골랐습니다.
두번째 점
첫번째 점이 12이니까 34,35,45 중에 아무것이나 골라도 됩니다. 현재까지 만들어진 path는 아래와 같습니다.
12-34
세번째 점
세번째 vertex로는 15 혹은 25가 나오면 됩니다. 1과 2의 대칭성에 의해 15를 골르는 것으로 충분합니다.
12-34-15
네번째 점
네번째 vertex로는 23이나 24가 나오면 됩니다. 여기서는 3과 4의 대칭에 의해 둘중에 아무것이나 고르면 됩니다. 저는 23을 골랐습니다. 그러면 현재까지 path는 아래와 같습니다.
12-34-15-23
다섯번째 점
다섯번째 vertex로는 14혹은 45를 선택하면 됩니다. 여기서는 14와 45를 고르냐에 따라 path가 달라집니다. 그래서 아래의 두가지 경우가 생깁니다.
- 12-34-15-23-14
여기서 다음vertex로 25 나 35를 선택하면 됩니다.
1. 12-34-15-23-14-25
25이후에는 13만 선택할 수 있습니다. 그래서 얻어지는 path는 12-34-15-23-14-25-13
2. 12-34-15-23-14-35
35이후에는 24만 선택할 수 있습니다. 그래서 얻어지는 path는 12-34-15-23-14-35-24 - 12-34-15-23-45
여기서 다음 vertex로는 13만 선택할 수 있습니다. 여기서 얻어지는 path는 아래와 같습니다.
12-34-15-23-45-13
13이후에는 24나 25를 얻을 수 잇습니다. 이를 종합하면 얻을 수 있는 path는 아래와 같습니다.
12-34-15-23-45-13-24
12-34-15-23-45-13-25
위와 같이 대칭성을 이용하고 petersen graph 의 특징을 이용하여 길이 6짜리 path를 얻었습니다.
- 12-34-15-23-14-25-13
- 12-34-15-23-14-35-24
- 12-34-15-23-45-13-24
- 12-34-15-23-45-13-25
이 path들의 마지막 점에는 1이나 2를 포함하고 있으므로 다음 vertex로 12가 나올 수 없습니다. 따라서 길이 7짜리 cycle은 존재하지 않습니다.
문제출처- 광주과학기술원 최정옥 교수님의 “그래프 이론” 수업 (2023년 가을학기) 중 Homework 2