문제출처
광주과학기술원(GIST) 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework2
Solution
(i). Assume that the Petersen graph has a cycle of length 7. Call this cycle ( C_7 ).
(ii). Each vertex in ( C_7 ) has two edges within the cycle. Since the Petersen graph is 3-regular, each vertex must have one additional edge connecting to a vertex outside of the cycle.
(iii). This additional edge cannot connect to another vertex within the cycle. The Petersen graph has a girth of 5, but if such connections existed, it would result in a girth of 3 or 4.
(iv). The Petersen graph has a total of 10 vertices, so these additional edges must connect to the remaining 3 vertices outside of ( C_7 ).
(v). Since the 3 vertices outside the cycle must connect to the 7 vertices of ( C_7 ), at least one of these outside vertices must be connected to 3 or more vertices of ( C_7 ) (by the pigeonhole principle).
(vi). If one outside vertex is connected to 3 vertices of ( C_7 ), it will create a cycle of length 4 (girth 4). This contradicts the property of the Petersen graph having a girth of 5.
감점이 있었던 것으로 기억합니다. 참고바랍니다.