Question

Let \(G\) be a simple plane graph with fewer than 12 faces, in which each vertex has degree at least 3 . (i) Use Euler's formula to prove that \(G\) has a face bounded by at most four edges. (ii) Give an example to show that the result of part (i) is false if \(G\) has 12 faces.

Short answer

By using Euler's formula and the given conditions, G must have a face bounded by at most four edges. However, this may not always hold true. For instance, in an octahedron graph with 8 vertices, 18 edges, and 12 faces, while every vertex has degree three, there are no faces that are bounded by four edges.

Step-by-step solution

Applying Euler's formula

Euler’s formula states that for any simple plane graph with V vertices, E edges, and F faces, we have \(V - E + F = 2\). Given that, each vertex has at least degree three, then the number of edges is at least \(3V/2\), because every edge is counted twice. Also, since the graph has F faces and each face has at least four edges, then the number of edges is at most \(4F/2\), once again as every edge appear in exactly two faces.

Result from Euler's formula and given conditions

So, for the given conditions we have \(3V/2 \leq E \leq 2F\) which is equivalent to \(3V \leq 4F\). And from Euler’s formula, we know that \(F = 2 - V + E\). Substitute the value of E from this in the earlier equation as \(3V \leq 4(2 - V + E)\). Hence, the graph has a face bounded by at most four edges.

Counter-example

Consider a graph with 8 vertices, 18 edges and 12 faces, (known as the octahedron). Every vertex has degree three, and each face is a triangle bounded by only three edges. This is a counter-example, as the graph has 12 faces, but there is no face bounded by four edges.

Key concepts

Simple Plane Graph

A simple plane graph is a type of graph that can be drawn on a plane without any edges crossing each other. The term 'simple' refers to the fact that such a graph does not contain any loops (edges that connect a vertex to itself) and does not have multiple edges between any two vertices — each pair of vertices is connected by at most one edge.

Understanding simple plane graphs is critical because they form the basis for many concepts in graph theory. They are used extensively in computer science, engineering, and mathematics to represent networks where cross-connections are not allowed or desirable. These graphs are also known for their beauty and symmetry, which is why they are often used in recreational mathematics and art.

One of the primary properties of a simple plane graph relates to its faces. When drawn on a plane, the edges of a simple plane graph divide the plane into regions called faces. The infinite region outside of the graph is also considered a face. Euler's Formula, which connects the number of vertices (V), edges (E), and faces (F) in a simple plane graph, becomes an elegant way to describe these interrelationships.

Vertex Degree

The concept of vertex degree in graph theory is essentially a count of how many edges are incident to—or touching—a vertex. For a simple graph, the degree of a vertex is simply the number of edges connected to it.

In the context of the exercise provided, the degree is particularly significant because the problem considers simple plane graphs where each vertex has a degree of at least three. This condition is crucial in making certain deductions about the graph's structure using Euler's formula.

For example, if we know that every vertex has a degree of at least three, we can infer that the total number of edges in the graph will be at least one and a half times the number of vertices. This is because each edge is counted twice in the sum of degrees (once for each end of the edge), which is a key detail in the problem-solving process. This characteristic helps establish lower bounds for edge count and plays a role in proving that such a graph must have a face bounded by at most four edges.

Graph Faces

Graph faces refer to the regions bounded by edges in a plane graph. In a simple plane graph, these faces are crucially important because they are part of the equation used in Euler’s formula (V - E + F = 2), where 'F' stands for the number of faces. Faces can be thought of as 'rooms' created by wall-like edges within the graph.

In the exercise, an understanding of graph faces is used to deduce certain properties of the graph. The requirement that each face be bounded by at least four edges would mean that every face consists of a polygon with at least four sides. However, by utilizing the constraints of Euler's formula, it is shown that there must be at least one face with four or fewer bounding edges.

The concept of faces is fascinating because it not only helps in proving theoretical propositions using Euler’s formula but also in visualizing and understanding the structure of a graph. Yet, the counter-example provided in the exercise demonstrates that these properties can have exceptions, exemplified by a graph that has exactly 12 faces but does not have any face bounded by four edges, illustrating the delicate balance between the number of vertices, edges, and faces in graph theory.