Discussion:
Q: Show that the Petersen graph is nonplanar by
a) showing that it has k3,3 as a subcontraction, and
Can you explain about contraction.
a) If the length of every cycle is at least k, then determine an upper bound B for m in terms of n and k.
b)Show that the bound B obtained in a) is sharp by determining for arbitrary k>=3, a plane graph G of order n and size B, every cycle of which has length at least k.
Note: if a planar graph is embedded in the plane ,then it is called a plane graph.
keywords: peterson graph