The Petersen graph has ten vertices, fifteen edges, and girth five. One way to verify the girth is its description by the two-element subsets of a five-element set, with adjacency meaning disjointness. A triangle would require three pairwise disjoint two-element subsets, which is impossible. Two distinct vertices have at most one common neighbor: the only possible common neighbor is a two-element subset of the complement of their union. Therefore a four-cycle is impossible. A five-cycle exists in its standard pentagon drawing.
If it were a planar graph, part (i) would give , a contradiction. Thus the Petersen graph is nonplanar. The held source has blank space where its drawing is mentioned; the named graph determines this argument without that missing illustration.
Articles by others on the same topic
There are currently no matching articles.