In two recent works, Akbar Ali, Gary Chartrand, and Ping Zhang conjecture that there is no regular link-irregular graph. Here “regular” means all vertices have equal degrees and “link-irregular” means all vertices induce non-isomorphic neighborhoods. In support of this conjecture, they show that it is true for degrees three and four. However, the probabilistic method shows this to be false for sufficiently high degrees.

The two works are:

Irregularity in Graphs, Springer Briefs in Mathematics, 2021, doi:10.1007/978-3-030-67993-4, Conjecture 2.1, page 25

“On link-irregular graphs”, Discussiones Mathematicae Graph Theory 45 (2025) 95–110, doi:10.7151/dmgt.2521, Conjecture 2.9, p. 106.

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 which allows us to preserve enough of the independence of a uniform (non-regular) random graph to make the analysis go through. The short version is that we take two random graphs, and add just enough edges connecting the two to combine them into a single regular graph. The neighborhoods of the vertices in the resulting bicameral graph are so big and sufficiently non-overlapping that any two isomorphic neighborhoods would lead to pairs of disjoint isomorphic induced subgraphs much larger than the ones that can be found in random graphs.

In more detail, choose two uniformly-random (n)-vertex graphs (G_1) and (G_2). Let (R) be the event that:

Both (G_1) and (G_2) have equal numbers of edges,

All vertices of both graphs have degree within (O(\sqrt{n\log n})) of (n/2), and

All pairs of vertices in the same graph have at most (n/4+O(\sqrt {n\log n})) shared neighbors.

The first of these conditions happens with probability (\Omega(\tfrac1n)), which we are going to consider to be a somewhat large probability. The other two conditions fail with a probability that (by Chernoff bounds) can be made smaller than any chosen polynomial by adjusting the constant in the (O)-notation. This is a small enough failure probability that condition (R) happens with overall probability (\Omega(\tfrac1n)).

If event (R) happens, then (G_1) and (G_2) have equal numbers of vertices and edges, and would need to be augmented by the same number of incidences to bring all vertex degrees up to equal the maximum degree. Choose a target degree (\Delta) larger than this maximum degree by (O(\sqrt {n\log n})), so that all vertices have roughly the same number of missing incidences (the difference between (\Delta) and the vertex degree in (G_1) or (G_2)). Think of each of these missing incidences as a “terminal”, attached to its vertex. Order the terminals in (G_1) so that each vertex has its terminals consecutive in the ordering, and order the terminals in (G_2) so that each two terminals from the same vertex are (\Omega(n)) positions apart. Pairing up the terminals from (G_1) and (G_2), in these two orders, gives a (nonrandom) set of edges connecting (G_1) to (G_2) that do not connect the same pair of vertices more than once. Let (G_R) be the (\Delta)-regular supergraph of (G_1\cup G_2) constructed in this way; it has (O(\sqrt{n\log n})) added edges per vertex.

If (G_R) exists and is to have two isomorphic neighborhoods of vertices (u) and (v), let (U) be any set of (n/4-O(\sqrt{n\log n})) members of (N(u)\setminus N(v)) belonging to the same subgraph (G_i) as (u), whose images under the isomorphism belong to the same subgraph (G_j) as (v). Then (U) induces a subgraph isomorphic to some other disjoint induced subgraph (G_j[V]). We can describe this situation as an instance of the following event (I):

• There exist two disjoint sets (U) and (V), each a subset of (G_1) or (G_2), that have size (n/4-O(\sqrt{n\log n})) and that induce isomorphic subgraphs in (G_1\cup G_2).

Now let’s analyze the probability of event (I). We can do this independently of whether event (R) also holds, because the definition of event (I) does not depend on the conditions of event (R). First, let’s count the expected number of isomorphisms between pairs of sets of this size. We can calculate this by multiplying the number of pairs of disjoint sets (U,V) of this size (exponential in (n)), the number of bijections between these sets (exponential in (n\log n)), and the probability that any particular bijection produces an isomorphism (inverse-exponential in (n^2)). By Markov’s inequality the probability that there exists even a single large-enough isomorphic pair is at most the same product. For large enough (n) the inverse-exponential-in-quadratic term wins and the probability of event (I) is tiny, also inverse exponential in a quadratic.

By the union bound (applied to the probabilities of not-(R) and (I)), the probability that (R) happens and (I) does not happen is (\Omega(\tfrac{1}{n})). This gives a lower bound on the more constrained event that (G_R) exists but does not have a pair of vertices with isomorphic neighborhoods (it is link-irregular). Because this probability is positive (for sufficiently large (n)), there exists a possible random choice for which (G_R) exists and is link-irregular. Its existence contradicts the conjecture of Ali, Chartrand, and Zhang. More generally, it shows that the conjecture is false for sufficiently large even numbers of vertices. By adjusting the target degree (\Delta) for an appropriate choice of (n), the same construction shows that the conjecture is false for all sufficiently large degrees.

(Discuss on Mastodon)