Question

Prove that a complete graph (a graph in which there is an edge between every pair of vertices has \(n^{n-2}\) spanning trees, Here \(n\) is the number of vertices in the graph.

Short answer

There are \(n^{n-2}\) distinct labelled trees or spanning trees in a complete graph with \(n\) vertices.

Step-by-step solution

Understanding the given

In a complete graph, there exists an edge between every pair of vertices. A Spanning Tree of a graph is a tree formed using the graph's vertices and a subset of the graph's edges. Our goal is to prove the relation between the number of vertices and the number of spanning trees in a complete graph, where the number of spanning trees is given by \(n^{n-2}\).

Considering the Prüfer Code

Prüfer code is a one-to-one correspondence between the set of labeled trees (trees where the vertices are distinct) with \(n\) vertices and the set of sequences with \(n-2\) elements. The code is constructed by removing vertices from the graph and noting the vertex of highest order that is connected to the removed vertex by an edge.

Proof Explanation

A complete graph with \(n\) vertices will have \((n-2)\) elements in the Prüfer code sequence, and each element can be any of the \(n\) vertices. As there is a one-to-one correspondence between Prüfer codes and spanning trees, there are \(n^{(n-2)}\) possible Prüfer sequences. Consequently, there are \(n^{(n-2)}\) distinct labelled trees or spanning trees in a complete graph with \(n\) vertices.

Key concepts

Complete Graphs

In graph theory, a complete graph is a simple concept filled with rich information. It's a type of graph where every possible connection between vertices is made. Imagine you have a group of people at a party, and everyone shakes hands with everyone else. That's similar to a complete graph, where every pair of vertices is connected by a unique edge. Such a graph is denoted as \(K_n\), where \(n\) represents the number of vertices.

Complete graphs are foundational in graph theory because they ensure maximum connectivity. They are crucial when studying properties like Hamiltonian paths and cycles, which exist in complete graphs due to the abundance of edges. The number of edges present in a complete graph \(K_n\) is given by the formula \(\frac{n(n-1)}{2}\).

This ensures every vertex can reach any other vertex directly, forming an all-inclusive network, which is why complete graphs are often used in scenarios requiring full connectivity.

Spanning Trees

A spanning tree is a unique kind of subgraph that includes all the vertices of the original graph but only the minimum number of edges needed to make it a tree. Think of it as a special path that includes no loops and connects all points efficiently.

In a complete graph, there are many spanning trees. Each spanning tree uniquely connects all vertices without creating any cycles. It's like removing redundant paths in the complete graph so that there's exactly one simple path between any two vertices.

For a complete graph with \(n\) vertices, the number of spanning trees can be substantially large due to the multitude of ways you can connect all nodes without forming loops. This is where Cayley's formula comes into play, showing that a complete graph with \(n\) vertices has \(n^{n-2}\) spanning trees. This formula reveals the extensive number of potential connections even within the simple structure of a spanning tree.

Prüfer Code

The Prüfer code provides a compact and efficient way to represent a labeled tree with \(n\) vertices using a sequence of \(n-2\) numbers. This unique representation has a one-to-one correspondence with spanning trees, making it particularly useful in enumerating these trees.

To generate the Prüfer code, the labeled tree is pruned by repeatedly removing the leaf (a vertex with degree 1) with the smallest label and recording its neighbor, until only two vertices remain. The sequence of neighbors forms the Prüfer code, offering a succinct encoding of the tree's structure.

What makes the Prüfer code fascinating is its application to counting spanning trees. Since each spanning tree corresponds to a unique Prüfer code, and the code is composed of \(n-2\) elements, each of which can be one of \(n\) different vertices, we derive that there are \(n^{n-2}\) different spanning trees for a complete graph with \(n\) vertices. This elegant solution highlights the power and utility of the Prüfer code in graph theory.