🔢 mathematics

Kemeny's constant and Braess cliques in graphs

This paper introduces the concept of Braess cliques ( $K_\ell$ ) as subgraphs that, when inserted into a graph, increase Kemeny's constant (average travel time), and demonstrates that such cliques exist for $\ell \geq 3$ in various graph families, including almost every connected planar labelled graph.

Original authors: Jane Breen, Emma deBlieck, Kevin N. Vander Meulen

Published 2026-08-06

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Jane Breen, Emma deBlieck, Kevin N. Vander Meulen

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a city where every street is a one-way path, and a delivery driver zips around, choosing their next turn completely at random. Sometimes they get stuck in a loop, sometimes they zip straight to the destination. In the world of mathematics, specifically a field called graph theory, we map these cities as "graphs"—dots (vertices) connected by lines (edges). Mathematicians have a special tool called Kemeny's constant to measure how long, on average, it takes for our random driver to get from one random spot in the city to another. Think of it as a "traffic congestion score" for the entire network: a lower score means the city is well-connected and easy to navigate, while a higher score means the driver is likely to wander aimlessly for a long time.

Usually, you'd think that adding a new road to a city would make traffic flow better, lowering that congestion score. But in the 1920s, a traffic engineer named Dietrich Braess discovered a mind-bending glitch: sometimes, adding a new road actually makes the whole system slower. It's like building a shortcut that causes everyone to jam up because everyone tries to use it at once. This is Braess's paradox. While we knew this could happen with a single new road (a "Braess edge"), a team of researchers wondered: what if we added a whole bunch of roads at once, connecting a group of isolated dots into a tight cluster? Would that help, or would it make the chaos even worse?

This paper, written by Jane Breen, Emma deBlieck, and Kevin N. Vander Meulen, dives into that exact question. They introduce a new concept called a Braess clique. Imagine a group of friends who all live on a dead-end street with no connections to each other. If you suddenly build a giant roundabout connecting all of them to each other, you'd expect traffic to improve. But the authors prove that in certain graph structures, doing exactly that—turning a group of isolated points into a fully connected "clique"—can actually increase the average travel time for the random walker. It's counter-intuitive: adding more connections makes the system less efficient.

The researchers didn't just guess; they used rigorous math to show exactly when and why this happens. They found that if you take a specific type of graph (like a tree with "pendant" vertices, which are like leaves on a branch) and connect a group of those leaves together, you can create a Braess clique. They proved that for almost every connected planar graph (think of a map you can draw on a piece of paper without lines crossing), you can find groups of three or more vertices that, when connected, will slow down the random walker.

Perhaps the most surprising discovery is how these "bad" connections interact. You might assume that if a single road is a "Braess road" (one that slows things down), then a whole bunch of them together would definitely be a "Braess clique." The authors show this isn't always true. They found examples where a group of roads forms a Braess clique, even though none of the individual roads in that group are Braess roads on their own. Conversely, they found groups where every single road is a Braess road, yet connecting them all together doesn't create a Braess clique. It's a bit like how adding a few bad ingredients to a cake might ruin it, but adding a whole bowl of them might somehow balance out in a weird way, or vice versa.

The paper also explores complete bipartite graphs (imagine two groups of people where everyone in Group A is friends with everyone in Group B, but no one in Group A is friends with anyone else in Group A). They calculated precise conditions for when adding a clique to one of these groups will backfire. For instance, in a graph with 90 people in one group and 10 in the other, adding a clique of up to 32 people makes the system worse, and the "worst" possible addition is a clique of exactly 33 people.

Ultimately, this work doesn't just find a few weird examples; it maps out the landscape of these paradoxes. It shows that the relationship between adding roads and traffic flow is far more complex than "more roads = better traffic." By understanding these "Braess cliques," mathematicians can better predict how networks—from social media connections to computer data flows—behave when we try to "fix" them by adding more links. The authors conclude that while we've found many ways to break a network by adding connections, there is still much to learn about the specific "accessibility" of different points in the network and how that drives these strange, counter-intuitive results.

Technical Summary: Kemeny's Constant and Braess Cliques in Graphs

Problem Statement
Kemeny's constant, $K(G)$ , serves as a spectral invariant measuring the expected length of a random trip between two randomly chosen vertices in a graph $G$ , where the selection is weighted by vertex degrees. A counter-intuitive phenomenon known as Braess' paradox occurs when adding an edge to a graph results in an increase in $K(G)$ , thereby reducing the graph's overall connectivity or "efficiency" from the perspective of a random walk. Such an edge is termed a "Braess edge." While the existence of Braess edges is established for various graph families (e.g., trees with pendent twins, complete multipartite graphs), the behavior of adding multiple edges simultaneously remains less explored. Specifically, this paper investigates the concept of a "Braess clique": an independent set of vertices such that inserting all possible edges between them (forming a clique) increases Kemeny's constant. The central questions are: under what conditions do Braess cliques exist, how do they relate to individual Braess edges, and what structural properties of a graph facilitate this phenomenon?

Methodology
The authors employ a combination of spectral graph theory, Markov chain analysis, and combinatorial matrix theory.

Markov Chain Formulation: The random walk on a graph is modeled as a Markov chain with transition matrix $T = D^{-1}A$ . Kemeny's constant is expressed spectrally as the sum of reciprocals of $(1 - \lambda_j)$ for non-trivial eigenvalues, or structurally via mean first passage times and the group inverse of $I-T$ .
Equitable Partitions and Quotient Matrices: A core methodological tool is the use of equitable partitions. When a graph contains a set of "twin vertices" (vertices sharing the same neighbor set), the transition matrix can be reduced to a smaller quotient matrix. The authors derive expressions relating the Kemeny's constant of the original graph to that of its quotient, allowing for the analysis of adding edges within the twin set without recalculating the full spectrum.
Accessibility Index: The paper utilizes the accessibility index, $\alpha_G(v)$ , which represents the expected time to reach vertex $v$ from a stationary start. The authors establish relationships between the accessibility indices of a graph before and after the addition of pendant vertices or cliques.
Structural Decomposition: For graphs with cut vertices or specific separations (1-separation), the authors apply formulas that decompose $K(G)$ into components based on subgraphs, facilitating the calculation of changes in $K(G)$ when edges are added.

Key Contributions and Results

Definition and Characterization of Braess Cliques: The paper formally defines a Braess clique $K_\ell$ as an independent set of $\ell$ vertices where the insertion of the complete graph $K_\ell$ increases $K(G)$ . The authors provide a general formula (Theorem 3.5) for the change in Kemeny's constant when a clique is added to an independent set of $k$ twin vertices with common degree $r$ . This formula depends on the accessibility index of the vertices and the graph's size.
Existence in Specific Graph Families:
- Graphs with Pendant Twins: The authors analyze graphs where $k$ pendant vertices are attached to a single vertex $v$ . They derive a sufficient condition (Corollary 4.5) for the resulting independent set to form a Braess clique: if the number of edges $m$ in the original graph satisfies $m > \frac{k+1}{4}$ .
- Complete Bipartite Graphs: Extending previous results on Braess edges in $K_{\ell, n-\ell}$ , the paper determines necessary and sufficient conditions for the existence of a Braess clique of order $k$ within one partite set (Theorem 4.7). The condition is $k < \frac{7\ell - 3n + 2}{5}$ .
- Planar Graphs: By adapting arguments from prior literature on Braess edges, the authors observe that almost every connected planar labeled graph possesses a Braess $K_\ell$ for any $\ell \ge 3$ (Corollary 4.6).
Interplay Between Braess Edges and Cliques: The paper challenges the intuition that a Braess clique must be composed entirely of Braess edges, nor that a clique of Braess edges must form a Braess clique.
- Theorem 5.1: Demonstrates that in the complete bipartite graph $K_{\ell, 2}$ (for $\ell \ge 4$ ), the edges incident to pairs of vertices of degree 2 are Braess edges, yet the coclique formed by these vertices does not form a Braess clique.
- Theorem 5.3: Constructs a family of graphs (involving spider graphs attached to a base graph) that possess a Braess $K_3$ where none of the three edges are individually Braess edges.
- Theorem 5.13: Provides an example of a Braess $K_3$ where exactly one edge is a Braess edge, while the other two are not.

Significance and Claims
The paper claims to advance the understanding of the structural mechanisms that cause Kemeny's constant to increase upon edge addition. The primary significance lies in demonstrating that the "Braess effect" is not merely a property of single edges but can be amplified or altered by the simultaneous addition of multiple edges forming a clique. The authors highlight that the relationship between Braess edges and Braess cliques is non-trivial:

A collection of Braess edges does not necessarily constitute a Braess clique.
A Braess clique may contain edges that are not Braess edges, or even contain no Braess edges at all.

The work suggests that the accessibility index is a critical parameter in predicting these phenomena. The authors conclude that while the existence of Braess edges is somewhat counter-intuitive, the existence of Braess cliques is even more so, as one might expect that adding a highly connected subgraph (a clique) would universally improve connectivity. The paper provides explicit constructions and algebraic conditions that delineate the boundaries where this intuition fails, offering a deeper structural insight into random walks on graphs. The authors modestly suggest that further exploration of the accessibility index's role and the magnitude of changes in $K(G)$ for graphs with large independent sets remains a fruitful area for future investigation.

More like this