The Gold Standard of Graph Theory | Equal Degree Sequences, Different Connectivity

Imagine a report on two fictional communication networks. Each contains six devices. Each device has exactly two undirected connections, and the networks contain six connections in total. A dashboard that displays only numbers of devices, edges and local degrees will make the two networks look indistinguishable.

Yet Network A lets any device reach any other through a sequence of links. Network B consists of two self-contained groups of three devices, with no link between the groups. Both summaries are arithmetically correct, but their implications for reachability differ completely.

This article constructs the two graphs explicitly rather than asking readers to trust a picture. We will calculate degrees, components, paths, shortest distances and simple resilience checks, then rewire the edges while preserving every degree. The example is invented and illustrates undirected graph theory; it is not a diagnosis of a real phone, transport or internet network.

The general lesson is not that node-degree statistics are useless. They say something precise about immediate neighbourhoods. The problem begins when a local statistic is used to answer a global question such as whether everyone can reach everyone else.

Contents · Next chapter

A simple undirected graph G=(V,E) has vertices V and a set E of unordered pairs of distinct vertices. We use V={1,2,3,4,5,6}. There are no self-loops, repeated parallel links, directions, edge weights or failed devices in the initial comparison.

The degree d(v) of a vertex v is the number of distinct edges incident on it. The degree sequence is usually the list of vertex degrees sorted into a specified order. In both of our examples, that list is (2,2,2,2,2,2); indeed every labelled vertex will have degree two.

The handshake lemma says the sum of all degrees is twice the number of edges: Σd(v)=2|E|. Here the sum is 6×2=12, so both networks have exactly six undirected edges. This is a valuable check on any proposed edge list, but it does not establish which particular vertices share those edges.

MIT’s Introduction to Network Models, Lecture 2 distinguishes the definitions of vertex, edge, degree, path, connectivity and components. Keeping those definitions attached to the model prevents accidental shifts between directed reachability and undirected neighbour counts.

Contents · Previous chapter · Next chapter

Let Network A have edge set E_A={(1,2),(2,3),(3,4),(4,5),(5,6),(6,1)}. In words, the six devices form one closed ring. Each device is linked to its immediate predecessor and successor on the ring.

Vertex 1 touches vertices 2 and 6. Vertex 2 touches 1 and 3. Vertex 3 touches 2 and 4; continue the same way around the cycle. Each of the six degrees is two, and the edge list contains exactly six distinct pairs.

This graph is the cycle C₆. To reach vertex 4 from vertex 1, one route is 1–2–3–4, and another is 1–6–5–4. To reach 5 from 2, a route is 2–1–6–5; alternatives also exist. The key is that a walk can traverse the ring to connect any pair of vertices.

Counting connections immediately next to a vertex cannot tell us how far its two neighbours connect. Here those links form a global ring. The ring’s structure, not simply a degree of two, gives it the reachability property we will use.

Contents · Previous chapter · Next chapter

Now give Network B the edges E_B={(1,2),(2,3),(3,1),(4,5),(5,6),(6,4)}. Vertices 1,2,3 form one triangle, and vertices 4,5,6 form another. No edge joins the groups.

Check each local degree rather than relying on intuition. Vertex 1 touches 2 and 3, vertex 2 touches 1 and 3, and vertex 3 touches 1 and 2. The same count holds for 4, 5 and 6 inside their triangle. The degree sequence remains (2,2,2,2,2,2), and there are six edges.

Despite having no isolated vertices, Network B is disconnected. A walk starting at vertex 1 remains inside {1,2,3}, because none of those three vertices has a neighbour in {4,5,6}. You cannot find a 1-to-5 path by taking more steps; a necessary connecting edge does not exist.

The difference between A and B is not concealed in a vague label like ‘network quality’. The two edge sets are observably different, and a single missing cross-group relationship explains exactly why a dashboard of degrees fails to settle global reachability.

Contents · Previous chapter · Next chapter

The two graphs share their vertex count, edge count, total degree and per-vertex degrees. They differ in their connected components: A has one component of six vertices, whereas B has two components of three vertices each.

A connected component is a maximal set of vertices within which every vertex can reach every other. A path between any two vertices in A stays within its single component. In B there are two maximal reachable sets and no path from one set into the other.

At the level of small cycles the distinction is also visible. A’s only simple cycle in this six-edge ring has length six. B contains two length-three cycles. This is not a claim that cycle counts are always sufficient to determine connectivity; in these two explicit examples they provide another correct distinguishing statistic.

The table below makes a useful quality-assurance test: if you accidentally report both as connected merely because every device has two links, you are answering a global property from an insufficient local summary.

Contents · Previous chapter · Next chapter

Connectivity can be defined without a matrix. A path between two vertices is a sequence that follows edges, with vertices not repeated in a simple path. A graph is connected when a path exists between every pair of vertices. MIT’s Design and Analysis of Algorithms notes state this reachability criterion in the language of paths and connected graphs.

In C₆, a pair of neighbouring vertices has distance one. Vertices two steps apart have distance two; opposite vertices such as 1 and 4 have shortest-path distance three. Every pair has finite distance, so the graph’s diameter is three under ordinary unweighted shortest paths.

Inside either triangle of B, every pair is adjacent and has distance one. Between the triangles, no finite path exists. One common convention denotes those cross-component distances by infinity; then the whole disconnected graph has no finite diameter, even though each separate triangle has diameter one.

Always state which convention and population a reported distance describes. An average computed only over reachable pairs in B can be small because it silently discards the unreachable pairs. That number is not a measure of successful connectivity across all six devices.

Contents · Previous chapter · Next chapter

A breadth-first search starting at vertex 1 gives a simple computational connectivity test. Visit 1, inspect its neighbours, add any unvisited neighbour to a queue, and repeat until the queue is empty. All visited vertices belong to the component containing 1.

In Network A, the search discovers 1, then 2 and 6, then progressively 3 and 5, then 4. All six vertices are reached. In Network B, the search can only discover 1, 2 and 3; the queue empties before any of 4, 5 or 6 is visited.

To identify every component, continue the search from a still-unvisited vertex. Starting again at 4 discovers 4,5,6, leaving two components. This procedure needs the adjacency information, not merely how many neighbours each vertex possesses.

With a conventional adjacency-list representation, a full breadth-first search visits each vertex and examines edges in time proportional to |V|+|E|. For six vertices it is easy to perform on paper; for a large graph it is a standard, auditable algorithmic approach.

Contents · Previous chapter · Next chapter

A particularly revealing operation converts Network B into Network A while preserving every node’s local degree. Remove edge (1,2) from the first triangle and edge (4,5) from the second. Then add cross-group edges (1,4) and (2,5).

Check the degrees. Vertex 1 loses neighbour 2 and gains 4. Vertex 2 loses 1 and gains 5. Vertex 4 loses 5 and gains 1; vertex 5 loses 4 and gains 2. Vertices 3 and 6 are unchanged. Every device still has degree two, and the edge count is unchanged.

The resulting edge set forms the single six-cycle 1–3–2–5–6–4–1. A degree-preserving edge swap has changed two disconnected components into one connected component. Neither average degree nor even the fully labelled vector of degrees detects the change.

Such edge-switch examples explain why degree-preserving network randomisation and null models may produce topologically different graphs. Degree conservation is not the same as component conservation, path conservation or the preservation of any particular operational service.

A connected-pair calculation that the degree table misses

An especially clear comparison counts reachable pairs of distinct vertices. With six vertices, there are C(6,2)=6×5/2=15 unordered vertex pairs. In the six-cycle Network A, every one of those fifteen pairs is reachable. The fraction of connected pairs is therefore 15/15=1, or 100%.

In Network B, the first triangle contributes C(3,2)=3 reachable unordered pairs, and the second contributes another three. That gives only six reachable pairs out of fifteen; the other nine pairs place one endpoint in each triangle and are unreachable. The fraction of connected pairs is therefore 6/15=0.40, even though all six vertices have degree two.

Counting reachable pairs illustrates the difference between a local and a global summary without requiring advanced mathematics. The degree sequence sees two neighbours at every vertex in both networks. The connected-pair statistic sees a difference between every pair communicating and sixty percent of all cross-device pairings lacking a path.

The denominator matters. If an analyst averages distances only over reachable pairs in Network B, all such distances equal one because each component is a triangle. Reporting that ‘average shortest route length is one’ without saying that nine cross-component pairs were excluded creates an overly reassuring operational description. A small observed travel distance is not evidence that everyone can reach everyone else.

Now consider removing one edge from Network A. The six-cycle becomes a connected path, so the reachable-pair fraction remains one although some routes become longer. Remove one edge inside a triangle of Network B and each triangle remains locally connected; the global reachable-pair fraction stays 0.40. The two systems react differently to edge removal in their connectedness and in their possible path lengths.

This example is intentionally small so a reader can enumerate all fifteen pairs. In large networks, analysts often use component labels, breadth-first search, union–find structures or spectral diagnostics to measure reachability efficiently. The correct method depends on whether the network is static, directed, weighted, temporal or subject to changing failure states.

Finally, connectivity survives relabelling. Renaming devices 1 through 6 does not turn two disconnected triangles into one connected ring; any graph isomorphism must preserve component counts and cycle structure. This is why the difference is structural rather than a consequence of how the original author happened to number the vertices.

Contents · Previous chapter · Next chapter

In the ideal six-cycle A, removing one edge leaves a single path on all six vertices, so the graph remains connected. Removing a second suitably chosen edge can split it into two paths. For undirected edge connectivity, at least two edge removals are needed to disconnect C₆.

In B, the whole network is already disconnected. Within either triangle, deleting one edge does not disconnect its three vertices; the other two edges still provide a route. Thus a local group may look robust while there is no global connection at all.

Similarly, removing one vertex from A leaves a connected path of five vertices. Removing one vertex from B leaves a two-vertex edge in one former triangle and an intact separate triangle; global disconnection persists. A claim about resilience should specify the initial connectivity requirement and what class of failure is being tested.

The lesson is especially relevant to network reports that emphasise high average degree, generous redundancy or local clustering. Those descriptors can be true without providing a path between the communities or systems that must communicate.

Contents · Previous chapter · Next chapter

The adjacency matrix records which labelled pairs share edges. For our simple graphs, A_ij=1 exactly when vertices i and j are neighbours. Its row sums equal the vertex degrees, so both adjacency matrices have row sum two in every row, yet their off-diagonal patterns differ.

The graph Laplacian L=D−A, where D contains the vertex degrees on its diagonal, also reveals more than the degree vector. The number of zero Laplacian eigenvalues equals the number of connected components in an undirected graph: one zero for C₆ and two for the disjoint triangles.

Those spectral facts are consistent with the explicit path proofs; they do not replace basic model validation. If edge directions, weights or self-loops enter the problem, the matrix definitions and connectivity criteria must be adjusted. The graphs in this lesson are unweighted, simple and undirected throughout.

A sound graph report chooses a summary according to the decision. Degree can describe local link capacity. Component counts and reachability describe global access. Shortest paths address routing distance. Bridges and cut sets address certain failure modes. No single one-number metric covers them all.

Contents · Previous chapter · Next chapter

Does minimum degree two guarantee a connected graph? No. Network B has every degree equal to two but contains two components. Positive or even moderately high local degree is not a proof of global reachability.

Can the same edge count guarantee the same number of components? No. Both examples have six edges and six vertices, but they have one and two components. Edge placement matters.

Can we describe all six-vertex simple graphs with every degree two? Each connected component in a finite simple 2-regular graph is a cycle of length at least three. On six vertices, the possible cycle-length partitions are six, or three plus three. That matches the two constructions exactly.

Practice A: list all six neighbours for A and B and verify the total of twelve vertex incidences. Practice B: perform a search from vertex 2 and name the full reached set in each graph. Practice C: perform the edge swap in Chapter 8 and write the resulting six-edge ring in the opposite traversal direction.

Finally, suppose a dashboard only records the counts (n=6,m=6,minimum degree=2). State precisely what can be concluded—no isolated vertices and six total edges—and what remains unknown: the number of components, the existence of cross-group paths and the graph’s global failure behaviour.

Contents · Previous chapter · Next chapter

The conclusion is exact: a degree sequence can be the same while connectivity differs. Network A and B are rigorous counterexamples built from six vertices and six edges, and the degree-preserving swap demonstrates how global structure can change without changing the degree of any vertex.

Return to The Gold Standard of Graph Theory for the definitions and further graph methods. For another information-loss example, compare Information Theory: Same Symbol Entropy, Different Entropy Rates. For spatial adjacency, visit Geostatistics: Same Histogram, Different Neighbourhood Patterns.

Established teaching references include MIT Introduction to Network Models, Lecture 2 and MIT Design and Analysis of Algorithms lecture notes. They supply general graph definitions and algorithms; the named Network A and B edge sets here are original worked constructions, not empirical findings from MIT.

Continue through The Gold Standard hub and How X Works. Before using a local count as a proxy for system-wide performance, check whether the property you care about actually follows from that count.

Contents · Previous chapter