Degree, connectivity, and special graph types
Count the edges at every vertex, add the counts up, and a rule appears that never fails. A few simple measurements like this sort graphs into families.
Click a vertex, then another, to add or remove an edge. Watch the degrees and the degree sequence update, and try to make every degree equal.
Sorted list of all vertex degrees
The degree of a vertex is the number of edges connected to it. The degree sequence (sorted list of all degrees) is a basic graph invariant, though non-isomorphic graphs can share one. A graph where every vertex has the same degree is called regular -- try making all degrees equal to see it happen.
Click two vertices to add an edge and watch the degree sum and 2|E| move together. Use Remove Edge to undo.
Click two vertices to add an edge between them
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. 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.
Click two vertices to toggle an edge, then press Find Components to color each connected group. Shuffle gives you a new graph.
Click two vertices to toggle an edge between them
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. 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.
Click through the graph families and compare their edge counts, regularity, and properties in the table.
Every vertex is connected to every other vertex
These fundamental graph families appear everywhere in mathematics and computer science. Each has unique structural properties and closed-form edge count formulas. 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.
Special graph types -- complete (Kn), cycle (Cn), path (Pn), star (Sn), and bipartite graphs each have known structural properties
Spot a mistake or have an idea?