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

3 Answers

0 like 0 dislike
0 like 0 dislike
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
0 like 0 dislike
0 like 0 dislike
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.
0 like 0 dislike
0 like 0 dislike
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.

No related questions found

33.4k questions

135k answers


33.7k users

OhhAskMe is a math solving hub where high school and university students ask and answer loads of math questions, discuss the latest in math, and share their knowledge. It’s 100% free!