Question

Can someone help me understand this proof that a complete graph with 5 vertices is not planar?

Answer 1

Euler's formula is a formula that necessarily applies to planar graphs that says that the number of Vertices minus the number of Edges plus the number of Faces equals 2; V - E + F = 2. Euler's formula is proved elsewhere, and taken as a given here.

By definition, a complete graph with 5 vertices has 5 vertices and 10 edges. Plugging that into Euler's formula tells us it must have 7 faces:

5 - 10 + F = 2

5 + F = 12

F = 7

2E = pF is an equivalency set up by the number of edges and faces and how they relate to each other (each edge has 2 faces and each face has p edges, on average).

A complete graph has no loops (an edge that starts and ends with the same vertex) and therefore cannot have a face with one edge.

A complete graph has no parallel edges (two or more edges that start and end with the same two vertices) and therefore cannot have a face with two edges.

So every face must have 3 or more edges. So p, the average number of edges per face, must be at least 3.

So if 2E = pF and p >= 3 then 2E >= 3F. But we've already established that E = 10 and F = 7 and plugging that in gives us

2\*10 >= 3\*7

20 >= 21

Which is a contradiction

Answer 2

I understand the first part but the inequality 2E = pF doesn't really make sense to me as it seems to imply that there could be a non-integer number of faces, and the logic that p >= 3 means that 2E >= 3F doesn't make sense to me either.

Answer 3

They use Euler's formula to determine that, were it possible, it would produce 7 'faces' (regions on the paper, including the area outside the graph).  The smallest region we can make (by number of edges involved) is a triangle (or other 3 sided region).  A 2 edged region would mean both edges connect the same pair of vertices and a 1 edged region would be an edge starting and ending on the same vertex, neither of which happen in K5.  So to make 7 faces we need at least 21 edges.  Except really we need half that since each edge will be part of the boundary of exactly 2 faces (one on each side).  So we need 10.5 edges, minimum, to construct the 7 faces in our hypothetical planar drawing, but K5 only has 10 edges.  So our hypothetical planar embedding cannot exist.