Identify the vertices of a Petersen graph in your drawing and explainwhy. (Note again that the vertex set of the Petersen graph is the collec-tion of 2-subsets of [5], for example, 13 means {1, 3}. Two vertices aband cd are adjacent iff {a, b} ∩ {c, d} =∅

문제출처

광주과학기술원(GIST) 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 2

Solution

The set ([5] = \{1, 2, 3, 4, 5\}) has the following 2-subsets:
[
12, 13, 14, 15, 23, 24, 25, 34, 35, 45.
]
These 10 subsets form the 10 vertices of the Peterson graph.

To determine adjacency, the rule is:
Two vertices (ab) and (cd) are adjacent if and only if (\{a, b\} \cap \{c, d\} =∅).

Example:

• Vertex (34) is adjacent to (12), (25), and (15), because they share no elements.
• Vertex (34) is not adjacent to (35), (24), (13), (14), (45), and (23), because they share elements.

최정옥 교수님 강의를 듣는 후배님들께,

이거 퀴즈에도 나오고, 기말고사까지 관련해서 나오는 중요한 내용이니 참고바랍니다.