Question

(i) Use Euler's formula to prove that, if \(G\) is a connected planar graph of girth 5 with \(n\) vertices and \(m\) edges, then \(m \leq 5 / 3(n-2)\). Deduce that the Petersen graph is non-planar. (ii) Obtain an inequality, generalizing that in part (i), for connected planar graphs of girth \(r\).

Short answer

For connected planar graphs of girth 5, the number of edges \(m\) is at most \(5 / 3(n - 2)\), which leads to the conclusion that the Petersen graph is non-planar. For connected planar graphs of arbitrary girth \(r\), a similar process leads to a generalized upper bound on the number of edges in terms of \(n\) and \(r\).

Step-by-step solution

Apply Euler's formula

Start with Euler's formula for connected planar graphs: \(n - m + f = 2\). We need to express \(f\) in terms of \(n\) and \(m\) (or vice versa), so solve for \(f\): \(f = m - n + 2\).

Upper bound on the number of edges in each face

The girth of the graph is 5, which means that every face is bordered by at least 5 edges. So, the total number of edges must be at least 5 times the number of faces. We write this as \(2m \geq 5f\), where the factor of 2 accounts for each edge being counted twice.

Substitute for \(f\) in the inequality

Substitute the expression for \(f\) from Step 1 into the inequality from Step 2 to get: \(2m \geq 5(m - n + 2)\).

Simplify the inequality to get the upper bound on \(m\)

Simplify the inequality to get (after multiplication and rearrangement): \(m \leq 5/3(n - 2)\). This is the upper bound on the number of edges for connected planar graphs of girth 5.

Non-planarity of the Petersen graph

The Petersen graph has 10 vertices and 15 edges. Substitute these values into the inequality obtained in Step 4: \(15 \leq 5/3(10 - 2)\). This simplifies to \(15 \leq 40/3\), which is false. So, the Petersen graph is non-planar.

Generalization to graphs of arbitrary girth

The same method applies to graphs of arbitrary girth \(r\). Begin with the Euler's formula, find the relationship between edges and faces based on the girth: \(2m \geq rf\), and solve for \(m\). The resulting inequality for the number of edges will be a generalization of the inequality obtained in Step 4 and will depend on the girth \(r\).

Key concepts

Euler's Formula

Euler's formula is a fundamental theorem in planar graph theory, providing a relationship between the number of vertices (), edges (), and faces () of any connected, planar graph. The formula states that for these graphs, - + = 2. This elegant equation underpins much of planar graph theory, offering insights into the properties and limitations of planar graphs.

To use Euler's formula effectively, one must understand each of the components involved. Vertices (), are the nodes or points of the graph. Edges () are the lines connecting the vertices, and faces () are the 2-dimensional regions bounded by edges, including the outer, infinite face.

When applying Euler's formula, as in the exercise, it's useful to rearrange it to solve for one of the variables. In the case of our exercise, we want to find the maximum number of edges (), therefore we isolate to find = 2 + - . This restructured version of Euler's formula forms the backbone of the provided solution, setting the stage for the entire argument and leading to the conclusion about the non-planarity of the Petersen graph.

Graph Girth

Graph girth is another critical concept in the study of graph theory. The girth of a graph is the length of its shortest cycle. In layman's terms, it's the smallest number of edges you must traverse to start and return to the same vertex without retracing your steps. Girth provides crucial information about a graph's structure, impacting properties like planarity.

Consider a graph with girth 5; this means that any cycle must have at least five edges. This fact becomes incredibly useful when analyzing how many edges a planar graph can have, as in our original exercise. Since each face of a planar graph is bounded by at least the number of edges equal to the girth, we know that for a face to exist in a graph of girth 5, it must be bounded by at least 5 edges. This insight allows for logical deductions about the number of faces and edges, contributing to the proof that leads to the upper bound of edges in such a graph.

Understanding girth is not only essential for solving theoretical problems but also has practical implications in network design and other fields where graph models are applied.

Petersen Graph Non-planarity

The non-planarity of the Petersen graph is a well-known result in graph theory, and it highlights the limitations of applying Euler's formula and the concepts related to graph girth.

The Petersen graph, with its 10 vertices and 15 edges, seems at first glance like it might be planar. However, upon applying Euler's formula and considering the inequality derived from the concept of girth, we can debunk this assumption. For a graph of girth 5 to be planar, Euler's formula tells us that it must satisfy the condition ≤ 5/3( - 2). When we plug in the Petersen graph's vertex and edge count into this inequality, it does not hold true, confirming its non-planarity.

This conclusion demonstrates how these principles serve not just in academic exercises, but as practical tools to analyze and categorize graphs. The non-planarity of the Petersen graph also has implications for problems such as network routing and the design of circuits, where planar graphs are preferred due to their simpler structure.