What is a Complete Graph?
In the world of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. In other words, every vertex is connected to every other vertex. A complete graph with n vertices is denoted by \(K_n\).
This property makes them fundamental structures in graph theory and they often appear as subgraphs in other, more complex graphs.
Properties of Complete Graphs
- A complete graph with n vertices has \(\frac{n(n-1)}{2}\) edges.
- They are regular of degree n-1.
- The chromatic number of \(K_n\) is n.
Visualizing Complete Graphs
Let’s look at a few examples to get a better feel for them.
Small Complete Graphs (K1, K2, K3)
Here are the first three complete graphs as disconnected components. You can drag the nodes around to see how they are structured.
- K1: A single vertex with no edges.
- K2: Two vertices connected by a single edge.
- K3: Three vertices forming a triangle.
The K4 Graph
This is a complete graph with 4 vertices and 6 edges.
The K5 Graph
And here is a complete graph with 5 vertices and 10 edges.
Generating Complete Graphs in Python
We can easily generate a complete graph using libraries like networkx. Here’s a simple Python script to create and visualize \(K_5\).
import networkx as nx
import matplotlib.pyplot as plt
# Create a complete graph with 5 vertices
n = 5
G = nx.complete_graph(n)
# Draw the graph
nx.draw(G, with_labels=True, node_color='skyblue', node_size=700, edge_color='purple')
plt.title("Complete Graph K5")
plt.show()
This script will generate a visual representation of the \(K_5\) graph we saw earlier.
Complete graphs are a cornerstone of graph theory, and understanding their properties is crucial for tackling more advanced topics. We encourage you to use the GraphArena playground to create your own complete graphs and explore their characteristics!