Combinatorics

PROBLEM 7.5. In this problem, you will prove that the Petersen graph is not planar. Let P denote the Petersen graph. The proof will be a proof by contradiction. We will assume that P can be drawn without edge crossings and then arrive at a contradiction. a) As we are assuming P is planar, let f be the number of faces in a planar drawing of P. Let n be the number of vertices of P and e the number of edges. What are n and e? Compute f using Euler's formula. --- ) b) Let li, l2,...,l, denote the lengths of the faces of the planar drawing of P. Show that li+l2 + ... +l= 2e. c) Every cycle of the Petersen graph has length at least 5, hence the integers li,l2,..., ls are all at least 5. Use this together with parts (a) and (b) to obtain the desired contradiction. aranh G is binartite if and PROBLEM 7.5. In this problem, you will prove that the Petersen graph is not planar. Let P denote the Petersen graph. The proof will be a proof by contradiction. We will assume that P can be drawn without edge crossings and then arrive at a contradiction. a) As we are assuming P is planar, let f be the number of faces in a planar drawing of P. Let n be the number of vertices of P and e the number of edges. What are n and e? Compute f using Euler's formula. --- ) b) Let li, l2,...,l, denote the lengths of the faces of the planar drawing of P. Show that li+l2 + ... +l= 2e. c) Every cycle of the Petersen graph has length at least 5, hence the integers li,l2,..., ls are all at least 5. Use this together with parts (a) and (b) to obtain the desired contradiction. aranh G is binartite if and