Question

Let \(G\) be a simple planar graph containing no triangles. (i) Using Euler's formula, show that \(G\) contains a vertex of degree at most 3 . (ii) Use induction to deduce that \(G\) is 4 -colourable. (In fact, it can be proved that \(G\) is 3 -colourable.)

Short answer

The proof begins by postulating and later contradicting that all vertices in the planar graph \( G \) have degree at least four, resulting in the discovery of a vertex with degree of at most three. The following step demonstrates that \( G \) is 4-colourable, utilising the principle of mathematical induction. Thus, a simple planar graph containing no triangles always contains a vertex of degree at most 3 and is always 4-colourable.

Step-by-step solution

Identify a vertex of degree at most 3

Let's suppose for contradiction that all vertices in \( G \) have degree at least 4. In a simple planar graph, each edge is counted twice when summing the degrees of all vertices, so the sum of all vertex degrees is \( 2E \). Therefore, it's \( 2E \geq 4V \). This can be simplified to \( E \geq 2V \).

Apply Euler's formula

According to Euler's formula, for a planar graph it's known that \( V - E + F = 2 \). Manipulating the equation, we can substitute for \( E \) to get \( V - 2V + F \leq 2 \). Simplifying gives \( F \geq V + 2 \).

Consider the absence of triangles

Since \( G \) doesn't contain any triangles, each face must be enclosed by at least four edges. Therefore, \( 2E = 4F \) or simplified, \( E \geq 2F \). Substituting \( F \) from step 2, we have \( E \geq 2(V + 2) = 2V + 4 \). But, it contradicts \( E \geq 2V \) derived before, so there must exist a vertex with degree at most 3.

Prove G is 4-colourable using induction

Now for the induction argument to prove that \( G \) is 4-colourable. Base Case: If \( G \) has at most 4 vertices, we can obviously colour it using at most 4 colours. Then we assume as induction hypothesis (I.H.) that any planar graph with fewer than \( n \) vertices is 4-colourable. For a graph with \( n \) vertices, let's remove a vertex \( v \) of degree at most 3, which we just proved exists. The remaining graph has fewer than \( n \) vertices, so by our I.H., it is 4-colourable. When we add back \( v \), it's only connected to at most 3 other vertices, which by Pigeonhole Principle, there's at least one colour left to colour \( v \) so that it doesn't share the same colour with its neighbours. Thus, \( G \) is 4-colourable.

Key concepts

Euler's formula

Understanding Euler's formula is essential when studying planar graphs in graph theory. In essence, Euler's formula establishes a relationship between the number of vertices (\(V\)), edges (\(E\)), and faces (\(F\)) of a simple, connected, planar graph. The formula is always expressed as \[ V - E + F = 2. \]
When applied to solve problems in graph theory, Euler's formula helps to derive important characteristics of the graph. For example, in the context of a simple planar graph with no triangles, Euler's formula can show that there must be a vertex with a degree less than or equal to 3. By exploiting the formula's relationship, we can manipulate the variables to pinpoint this specific vertex, leading to critical insights into the graph's coloring and structure.

Induction on graphs

Induction is a powerful mathematical technique used in graph theory to prove statements about graphs systematically. The process of induction on graphs involves two major steps:

• Base Case: You prove the statement for a graph (or graphs) of a certain minimum size, such as a starting point.
• Induction Step: You assume the statement is true for graphs smaller than a certain size and then prove it for graphs exactly that size.

Applying induction to planar graph coloring, we assume that any planar graph with fewer vertices than our subject graph \(G\) is 4-colorable. After removing a strategically chosen vertex, we use this assumption to color the rest of the graph, before finally reintegrating the removed vertex and ensuring it can also be colored while maintaining the planar graph's colorability constraints.

Graph theory

Graph theory is a fascinating area of mathematics, which studies properties and applications of graphs - structures made up of vertices (or nodes) connected by edges. It plays a crucial role in various fields, from computer science to physics and even social sciences.
A core aspect of graph theory is investigating how graphs can be colored, that is, assigning colors to vertices so that no two adjacent vertices share the same color. This simple premise leads to incredibly complex and interesting problems, such as the one presented in the exercise. Properly coloring a planar graph, for instance, has implications in fields like cartography, where neighboring regions on a map must be distinctively marked.

Simple planar graphs

A simple planar graph is a graph that can be drawn on a plane without any edges crossing. These graphs are fascinating for several reasons, not least because they relate to so many real-world scenarios such as network designs or map layouts.
When approaching such graphs, several rules come into play. For example, due to their planar nature, there's a certain limit on how many edges a graph can have relative to its vertices, and this cap influences the graph's properties, like its colorability. The constraint that the graph contains no triangles (subgraphs with three interconnected vertices) further influences its structure, creating interesting challenges in problems like the coloring of such graphs.