<p>Yes, even after two iterations. This follows from Babai–Erdős–Selkow. They show that for random <span class="math-container">$n$</span>-vertex graphs (Erdős–Rényi with probability 1/2) with probability at least <span class="math-container">$1-1/n^7$</span>, the following holds:</p>
<ol>
<li>The largest <span class="math-container">$\lceil 3 \log_2 n \rceil$</span> degrees are distinct.</li>
<li>Let <span class="math-container">$U$</span> be the set of vertices with degrees as above. Then no two other vertices in the graph have the same set of neighbors in <span class="math-container">$U$</span>.</li>
</ol>
<p>The top degrees are identified in the first round of 1-WL, and then the neighbors within those are determined in the next round. After that, all vertices have unique colors.</p>

CC BY-SA 4.0
2024-09-24T18:00:29.220Z
Very interesting, thanks! here is the paper if necessary https://epubs.siam.org/doi/abs/10.1137/0209047

Just out of curiosity, is it known whether the same is true or not with just one iteration?
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2024-09-24T18:04:15.107Z
If by "1 iteration" you mean just the degrees of the vertices, then it is false. To get it down to no automorphisms you'd need all vertices to have distinct degrees, which is impossible.
Joshua Grochow
CC BY-SA 4.0
2024-09-24T21:15:18.770Z
Ah yes of course that's quite obvious -- any nontrivial graph contains two vertices with the same degree. Thanks! (and sorry, that was a bit of a thoughtless question)
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2024-09-24T17:49:06.333Z
2024-09-24T18:32:20.527Z
2024-09-24T18:32:20.527Z
Joshua Grochow
<p>Based on color refinement, the 1D Weisfeiler Leman graph isomorphism test successfully distinguishes almost all non-isomorphic pairs of simple graphs. [1]</p>
<p>Can we also prove that the color refinement algorithm finds the exact automorphism group of almost all graphs, in the sense that the automorphism group of the string of resulting vertex 'colors' is identical to that of the graph? (+ What if we stop after k&gt;0 iterations?)</p>
<p>Almost all graphs have no symmetries (trivial automorphism groups) [2], so it would be sufficient to prove that all returned vertex colors are distinct on almost all such graphs.</p>
<p>[1] Babai, László and Kučera, Luděk (1979). Canonical labelling of graphs in
linear average time. In 20th Annual Symposium on Foundations of Computer
Science (SFCS 1979). IEEE, pp. 39–46.</p>
<p>[2] Bollobás, Béla (2001). Random Graphs (Chapter 9). 2nd ed. Cambridge Studies in Advanced
Mathematics. Cambridge.</p>

<graph-theory><graph-algorithms><graph-isomorphism>
Does color refinement find the exact automorphism group of almost all graphs?
Julius Kunze
# Does color refinement find the exact automorphism group of almost all graphs?

(Asked by: username_0 on 2024-09-23)

Based on color refinement, the 1D Weisfeiler Leman graph isomorphism test successfully distinguishes almost all non-isomorphic pairs of simple graphs. [1]

Can we also prove that the color refinement algorithm finds the exact automorphism group of almost all graphs, in the sense that the automorphism group of the string of resulting vertex 'colors' is identical to that of the graph? (+ What if we stop after k>0 iterations?)

Almost all graphs have no symmetries (trivial automorphism groups) [2], so it would be sufficient to prove that all returned vertex colors are distinct on almost all such graphs.

[1] Babai, László and Kučera, Luděk (1979). Canonical labelling of graphs in
linear average time. In 20th Annual Symposium on Foundations of Computer
Science (SFCS 1979). IEEE, pp. 39–46.

[2] Bollobás, Béla (2001). Random Graphs (Chapter 9). 2nd ed. Cambridge Studies in Advanced
Mathematics. Cambridge.

**Tags:** graph-theory, graph-algorithms, graph-isomorphism

---

## 1 answers

### Answer by username_1 on 2024-09-24. Score: 5 | Accepted answer

Yes, even after two iterations. This follows from Babai–Erdős–Selkow. They show that for random $n$-vertex graphs (Erdős–Rényi with probability 1/2) with probability at least $1-1/n^7$, the following holds:

1. The largest $\lceil 3 \log\_2 n \rceil$ degrees are distinct.
2. Let $U$ be the set of vertices with degrees as above. Then no two other vertices in the graph have the same set of neighbors in $U$.

The top degrees are identified in the first round of 1-WL, and then the neighbors within those are determined in the next round. After that, all vertices have unique colors.

> **Comments:**
> **username_2**: Very interesting, thanks! here is the paper if necessary https://epubs.siam.org/doi/abs/10.1137/0209047  Just out of curiosity, is it known whether the same is true or not with just one iteration?  
> **username_1**: If by "1 iteration" you mean just the degrees of the vertices, then it is false. To get it down to no automorphisms you'd need all vertices to have distinct degrees, which is impossible.  
> **username_2**: Ah yes of course that's quite obvious -- any nontrivial graph contains two vertices with the same degree. Thanks! (and sorry, that was a bit of a thoughtless question)  

---

