Question

Find the cycle and cutset ranks of (i) \(K_{5}\); (ii) \(K_{3,3}\); (iii) \(W_{5}\) : (iv) \(N_{5}\); (v) the Petersen graph.

Short answer

The cycle and cutset ranks are: for \(K_{5}\) (6,6), for \(K_{3,3}\) (4,4), for \(W_{5}\) (6,6), for \(N_{5}\) (1,1), and for the Petersen graph (6,6)

Step-by-step solution

Graph \(K_{5}\)

The graph \(K_{5}\) is a complete graph with 5 vertices. Therefore, the number of edges is \(n(n - 1) / 2=5(5-1)/2=10\). As a complete graph is maximal acyclic, the cycle rank is the number of edges minus the number of vertices plus 1, which is \(10 - 5 + 1 = 6\). The cutset rank is the number of edges minus the number of vertices plus 1, which is the same as the cycle rank, so the cutset rank is also 6.

Graph \(K_{3,3}\)

The graph \(K_{3,3}\) is a complete bipartite graph with 3 vertices in each set. Therefore, the number of edges is \(m \cdot n=3 \cdot 3=9\). The cycle rank is the number of edges minus the number of vertices plus 1, which is \(9 - 6 + 1 = 4\). The cutset rank is the number of edges minus the number of vertices plus 1, which is also 4.

Graph \(W_{5}\)

The graph \(W_{5}\) is a wheel graph with 5 vertices. Therefore, the number of edges is \(2n=2 \cdot 5=10\). The cycle rank is the number of edges minus the number of vertices plus 1, which is \(10 - 5 + 1 = 6\). The cutset rank is the number of edges minus the number of vertices plus 1, which is also 6.

Graph \(N_{5}\)

The graph \(N_{5}\) is a crown graph with 5 vertices in each set. Therefore, the number of edges is \(m \cdot (m-1)/2=5 \cdot 4/2=10\). The cycle rank is the number of edges minus the number of vertices plus 1, which is \(10 - 10 + 1 = 1\). The cutset rank is the number of edges minus the number of vertices plus 1, which is also 1.

Petersen Graph

The Petersen graph is a special, predefined graph with 10 vertices and 15 edges. The cycle rank is the number of edges minus the number of vertices plus 1, which is \(15 - 10 + 1 = 6\). The cutset rank is the number of edges minus the number of vertices plus 1, which is also 6.

Key concepts

Cycle Rank

In graph theory, the cycle rank of a graph provides insight into its complexity by measuring how many edges need to be removed to eliminate all cycles, transforming it into a tree (an acyclic graph). The rank is calculated through a straightforward formula: take the number of edges, subtract the number of vertices, and then add 1. This can be mathematically expressed as: \[\text{Cycle Rank} = |E| - |V| + 1\] where

• |E| is the total number of edges in the graph, and
• |V| is the number of vertices in the graph.

For example, consider the Petersen Graph, which is a famous non-planar graph with 10 vertices and 15 edges. By applying the formula, we find that its cycle rank is 6, indicating a reasonable level of complexity.

Cutset Rank

The cutset rank, also known as the cyclomatic number, provides another perspective on a graph's structure by focusing on its capacity constraints. It represents the minimum number of edge cuts required to separate the graph into two disjoint subgraphs. Like the cycle rank, this is a measure of the graph's connectivity and potential bottlenecks. The cutset rank is calculated with the same formula as the cycle rank: \[\text{Cutset Rank} = |E| - |V| + 1\] This formula highlights that for any connected graph, both the cycle rank and the cutset rank are numerically equivalent. For instance, in the complete graph \(K_5\), which has 5 vertices and 10 edges, the cutset rank is calculated as 6, equivalent to the cycle rank, conveying a high level of connectivity.

Complete Graph

Complete graphs are fundamental structures in graph theory where every pair of distinct vertices is connected by a unique edge. This means that in a complete graph with \(n\) vertices, the number of edges is given by: \[\frac{n(n-1)}{2}\] This results in a highly connected graph with no isolated vertices or disjoint subgraphs. Complete graphs are usually denoted as \(K_n\), where \(n\) is the number of vertices. For example, \(K_5\) has 5 vertices and 10 edges. Key features of complete graphs include:

• High connectivity, valuable in network design to ensure robustness.
• Serve as a basis for understanding more complex graph properties.
• All cycle ranks and cutset ranks are equal, indicating consistent connectivity.

Petersen Graph

The Petersen Graph is a rich object of study within graph theory due to its unique properties. Defined by its 10 vertices and 15 edges, the Petersen Graph does not fit easily into categories like planar graphs, as it cannot be drawn in a plane without edges crossing. This non-planarity makes it an important example in graph theory. Some features of the Petersen Graph include:

• Regular: Each vertex is of degree 3, meaning each connects to 3 other vertices.
• Symmetric: Offers a high level of symmetry, contributing to its aesthetic and theoretical appeal.
• Cubic and Non-Hamiltonian: Contains no Hamiltonian circuit, making it a clear counterexample in related conjectures.

Its cycle and cutset rank both equal 6, reinforcing its connected nature while maintaining its complexity, therefore serving as a versatile component in various problems and proofs.