Question

Find the thickness of (i) the Petersen graph; (ii) the 4 -cube \(Q_{4}\).

Short answer

The thickness of the Petersen graph is 2, and the thickness of the 4-cube \(Q_{4}\) is also 2.

Step-by-step solution

Determining Thickness of the Petersen graph

The Petersen graph is already well-studied and it is known that its thickness is 2. This is because you cannot draw a Petersen graph without edges crossing each other in a plane, but you can draw it as two planar graphs, which means it can be decomposed into two planar graphs.

Understanding the 4-cube Graph

A 4-cube graph, also known as hypercube graph, is a 4 dimensional cube. It is bipartite and regular, with every vertex being connected to 4 others. Its number of vertices is \(2^{4} = 16\) and number of edges is \(4 \times 2^{(4-1)} = 32\).

Calculating Thickness of the 4-cube Graph

Applying Euler's formula \(v - e + f = 2\) (for planar graph, where v is vertices, e is edges, f is faces), we solve for f to get \(f=e-v+2\). Since a planar graph requires at least three edges per face (i.e \(f \geq \frac{2e}{3}\)), we substitute \(f\) in the inequality to get \(\frac{2e}{3} \leq e-v+2\), which simplifies to \(v \geq \frac{e}{3} + \frac{4}{3}\). Substituting the number of edges \(e=32\) and vertices \(v=16\) for 4-cube, we find that t is 2. Thus, the 4-cube has a thickness of 2.

Key concepts

Petersen graph

The Petersen graph is one of the most famous graphs in mathematics. It is a non-planar graph that consists of 10 vertices and 15 edges. One of the key properties of the Petersen graph is its thickness. The thickness of a graph is the minimum number of planar subgraphs into which the graph can be decomposed. For the Petersen graph, this thickness is 2.

• This means it's impossible to draw the Petersen graph in a plane without any edges crossing each other.
• However, it can be partitioned into two separate planar graphs, meaning that it can be represented as two planar subgraphs laid on top of each other, illustrating its thickness of 2.

This feature makes the Petersen graph an interesting subject in the study of graph theory as it demonstrates the notion of graph thickness in a non-trivial manner.

4-cube graph

The 4-cube graph, also known as the hypercube graph, is a fascinating structure in higher-dimensional graph theory. It can also be referred to as a 4-dimensional cube. Here are some fundamental properties:

• A 4-cube graph is bipartite, meaning its vertices can be divided into two disjoint sets where no two vertices within the same set are adjacent.
• It is highly regular, with each vertex connected to exactly four others.
• The graph consists of 16 vertices, with each vertex representing a corner of a 4-dimensional cube.
• In total, it has 32 edges, which connect these vertices.

When considering the thickness of the 4-cube graph, we determine its decomposition into planar subgraphs.
By using Euler's formula, we find that the thickness of the 4-cube graph is also 2; meaning that just like the Petersen graph, it can be drawn using two overlapping planar graphs.

Planar graphs

Planar graphs are graphs that can be drawn on a plane without any edges crossing. In other words, these graphs can be embedded in a plane such that no two edges intersect except at their endpoints. Some important aspects of planar graphs include:

• Planar graphs follow Euler's formula: \(v - e + f = 2\), where \(v\) is the number of vertices, \(e\) is the number of edges, and \(f\) is the number of faces in the graph.
• For any graph to be planar, it must satisfy the inequality: \(f \geq \frac{2e}{3}\), ensuring enough faces for a given number of edges.
• Common examples of planar graphs are simple shapes like triangles and squares; however, more complex structures like the Petersen graph are non-planar.

Planar graphs are central to many problems in graph theory and offer a foundational understanding for exploring complex graphs, such as calculating the thickness of non-planar graphs, like the ones discussed earlier.