Posted on December 21st 2025, tagged graph-theory

In a recent blog post, David Eppstein proves the existence of regular link-irregular graphs. Those are graphs where all vertices have the same degree and where the subgraphs induced by vertex neighborhoods, called links, are all non-isomorphic. With this, he shows that a conjecture by Akbar Ali, Gary Chartrand and Ping Zhang is false (Conjecture 2.1 of [1] or Conjecture 2.9. of [2]).

David Eppstein prefaces the description of his construction with:

I’m pretty sure sufficiently large and high-degree uniformly random regular graphs provide counterexamples but those are difficult to prove things about. Instead I have the following more complicated construction […]

I was pretty sure of this as well, so I decided to give it a try and ultimately managed to prove the following variant:

For a fixed r≥3r \ge 3, a uniformly random (n−1−r)(n - 1 - r)-regular graph GG is asymptotically almost surely (a.a.s.) link-irregular.

I think this is a stronger notion of being high-degree than necessary for this to hold, but it is what I could prove without getting too deep into the weeds of uniformly random regular graphs.

I’ll denote the link for vv in GG, defined to be G[N(v)]G[N(v)], by LG(v)L_G(v), or L(v)L(v). I’ll also introduce a complementary notion of an unlink that removes a target vertex along with its neighborhood, i.e. G−N[v]G - N[v], denoted by UG(v)U_G(v) or U(v)U(v).

The complemented links of a graph correspond to the unlinks of its complement, as we have LG(v)‾=UG‾(v)\overline{L_G(v)} = U_{\cG}(v). Thus, a graph GG is link-irregular if and only if G‾\overline G is unlink-irregular.

Instead of directly working with a high-degree GG, this allows us to work with its complement G‾\overline G, which is a uniformly random rr-regular graph. To avoid littering everything with overlines, let’s restate what we want to prove in terms of rr-regular graphs directly:

For a fixed r≥3r \ge 3, a uniformly random r-regular graph GG is a.a.s. unlink-irregular.

Here we’re going to use a result by Béla Bollobás [3], who showed that GG’s vertices are a.a.s. uniquely identified by their distance seqeuences (di(v))i≥2(d_i(v))_{i\ge 2} where di(v)d_i(v) is the number of vertices at a distance ii from vv in GG. (We can start at distance 22, since d1(v)=deg⁡v=rd_1(v) = \deg v = r for all vv)

We can partition the vertices of a rr-regular graph by their distance from vv by first removing vv and then iteratively removing all vertices with a degree less than rr. The vertices removed in each iteration are exactly the remaining vertices adjacent to the vertices previously removed. Hence the first iteration removes vv’s neighbors, the second iteration all distance-22 vertices, then the distance-33 vertices, etc.

We can write this as the following recurrence: H0(v)=GD0(v)={v}Hi(v)=Hi−1−Di−1(v)Di(v)={ v∈VHi(v)∣deg⁡Hi(v)(v)<r }\begin{align*} H_0(v) &= G \ D_0(v) &= {v} \ H_i(v) &= H_{i-1} - D_{i-1}(v) \ D_i(v) &= {, v \in V_{H_i(v)} \mid \deg_{H_i(v)}(v) < r ,} \end{align*}

From this, we obtain the distance sequence for vv as di(v)=∣Di(v)∣d_i(v) = |D_i(v)|.

Next, observe that H2(v)H_2(v) removes vv and its neighbors, i.e. H2(v)=G−N[v]H_2(v) = G - N[v], so it is the same as vv’s unlink U(v)U(v). Also note that given any Hi(v)H_i(v) we can compute Dj(v)D_j(v) and Hj(v)H_j(v) for all j≥ij \ge i. Thus, we can compute (di(v))i≥2(d_i(v))_{i \ge 2} given only U(v)U(v). Since we can a.a.s. distinguish all vertices vv by their distance sequence (di(v))i≥2(d_i(v))_{i \ge 2} and since we can compute this given only their unlinks U(v)U(v), all of G’s unlinks must be a.a.s. non-isomorphic.

References

[1]

Akbar Ali, Gary Chartrand, and Ping Zhang. 2021. Locally irregular graphs. In Irregularity in graphs. Springer briefs in mathematics. Springer International Publishing, Cham, 13–26.↩︎

[2]

Akbar Ali, Gary Chartrand, and Ping Zhang. 2025. On link-irregular graphs. Discussiones Mathematicae Graph Theory 45, 1 (2025), 95–110.↩︎

[3]

Béla Bollobás. 1982. Distinguishing vertices of random graphs. In Graph theory, Béla Bollobás (ed.). North-holland mathematics studies 62. North-Holland, Amsterdam, 33–49.↩︎