Proof That a Simple Connected Planar Graph with Every Face of Degree 3 Has an Even Number of Faces

When working with planar graphs, a common question is how to determine whether a graph with specific face degrees results in an even or odd number of faces. In this article, we explore the proof that for a simple connected planar graph (planar graph) with at least three vertices, where every face has a degree of three, the number of faces (face degree) is always even.

Understanding the Definitions

Before diving into the proof, let's clarify some key terms:

Face Degree: The degree of a face in a graph is the number of edges that form the boundary of that face. Faces: In a planar graph, a face is a region bounded by edges, including the outer unbounded region.

Given Conditions

We start with a simple connected planar graph G with the following properties:

Planar graph: Ensures that the graph can be drawn in a plane without any edges crossing each other. F: Number of faces in G. E: Number of edges in G. V: Number of vertices in G. Every face of G has a degree of three.

Proof Steps

To prove that the number of faces in G is even, we follow these steps:

Step 1: Using the Degree of Faces

Since every face has a degree of three, each face contributes exactly three edges to the graph. However, each edge is counted twice because it belongs to two different faces. Therefore, we can write the following equation:

3F 2E

Rearranging this equation, we get:

F frac{2E}{3}

Step 2: Using Euler's Formula

Euler's formula for a simple connected planar graph is:

V - E F 2

By substituting F from the previous equation into Euler's formula, we get:

V - E frac{2E}{3} 2

Multiplying through by 3 to eliminate the fraction:

3V - 3E 2E 6

This simplifies to:

3V - E 6 quad text{or} quad E 3V - 6

Step 3: Substituting Back to Find F

Substituting the expression for E back into the equation for F, we get:

F frac{2E}{3} frac{2(3V - 6)}{3} 2V - 4

Step 4: Analyzing F

Given that each graph must have at least three vertices, we analyze F as follows:

For V 3: F 2(3) - 4 2 quad text{(even)} For V 4: F 2(4) - 4 4 quad text{(even)} For V 5: F 2(5) - 4 6 quad text{(even)} As V increases, F will always be of the form 2V - 4.

Conclusion

Since 2V - 4 is clearly even for all V geq 3, we conclude that if every face of the simple connected planar graph G has a degree of three, then G must have an even number of faces.
Thus, we have proved that if every face of G has a degree of three, then F is even.