Consider the following graph Petersen graph Prove that this

Consider the following graph (Petersen graph). Prove that this graph is not bipartite. Prove that this graph is not planar

Solution

(a) Color the vertices along the cycle alternately 5 Red and 5 Blue. Each vertex now has at least two neighbours of the opposite color.

But starting with two adjacent vertices of the same color (must exist on a non-bipartite graph), there is only one way to complete a 2-coloring, with at least two neighbors of the opposite color to every vertex. It turns out that 6 vertices get one color and 4 get the other which is a contradiction.

(b) As we know the Petersen graph has 10 vertices and 15 edges. But in a planar graph, the fundamental requirement is V+F-E=2 and in Petersen graph, that would be 10+F-15 = 2, which means it has 7 faces. The minimal cycle in Petersen is 5, so it would need to be made from pentagons, hexagons, or larger polygons.

Let we consider a pentagon case:7 pentagons = 35 edges or more and half of that rounded down to 17 edges. Each edge can only be used twice, and we\'ve gone over.