Consider the Petersen graph.
(a) Does it have a Hamilton Path?
(b) Does it have a Hamilton Path between any pair of non-adjacent vertices?
(c) Does it have a Hamilton Circuit?
Can the vertices of the Petersen graph be labelled with 2-subsets of {1, 2, 3, 4, 5} so that v is adjacent to w if and only if their subset labels are disjoint?
Imagine “shrinking” an edge e joining vertices a and b in some drawing of a planar graph G = (V, E).
Shrinking edge e does not introduce any edge-crossing. If we denote the graph that results from shrinking edge e by G \ e, then we know that if G is planar then G \ e is also planar.
(a) Explain why if H is obtained by shrinking a finite sequence of edges of G and H is not planar then G could not have been planar.
(b) Choose a sequence of edges in the Petersen Graph to shrink to obtain K5, and thereby prove (again) that the Petersen Graph is not planar.