= Solution
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 $15\le(5/3)(10-2)=40/3$, a contradiction. Thus \b[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.
Back to article page
