Degree, connectivity, and special graph types
Now that you understand the basic structure of graphs, it is time to explore their properties. These characteristics help us classify graphs, prove theorems, and understand the behavior of networks.
You will discover the elegant Handshaking Lemma, learn how to identify connected components, and meet some famous graph families -- complete, cycle, path, star, and bipartite graphs.
The degree of a vertex is the number of edges connected to it. Click a vertex, then click another to add or remove an edge and watch degrees update in real-time.
Sorted list of all vertex degrees
Key insight: The degree sequence (sorted list of all degrees) characterizes a graph. A graph where every vertex has the same degree is called regular -- try making all degrees equal to see it happen.
The Handshaking Lemma states that the sum of all vertex degrees equals twice the number of edges. Each edge contributes +1 to the degree of both its endpoints. Add edges and verify the identity.
Click two vertices to add an edge between them
Key insight: Since the sum of degrees is always even (2|E|), the number of vertices with odd degree must itself be even. This simple corollary has surprisingly powerful consequences in combinatorics.
A graph can have multiple connected components -- groups of vertices where you can reach any vertex from any other within the same group. Isolated vertices form their own component.
Click two vertices to toggle an edge between them
Key insight: BFS or DFS can identify all connected components in O(V + E) time. A graph is connected if and only if it has exactly one component.
These fundamental graph families appear everywhere in mathematics and computer science. Each has unique structural properties and closed-form edge count formulas.
Every vertex is connected to every other vertex
Key insight: Knowing a graph belongs to a named family immediately tells you its edge count, regularity, and many algorithmic properties. For example, Kn always has n(n-1)/2 edges and is (n-1)-regular.