Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
MATH 2601 - FoMP - Homework 5
Problem 1. Suppose that G is a planar graph on n vertices and m ≥ 2 edges, but with no 3-cycles. Then show that m ≤ 2n − 4.
Hint: As in the proof done in class, use the Euler characteristic that n−m+f = 2, for a connected planar graph drawn in the plane with f = #faces, and n and m being as above.
Problem 2. Show that K5 and K3,3 are nonplanar, using the upper bounds on the number of edges in a planar graph.
Additionally, the following problems from Hammack’s book: Chapter 8: 2, 8, 18 Section 11.1: 8, 16 Section 11.2: 4, 6, 10