Undirected graph with global bound on degree of vertices

Question

Let $G$ be an undirected graph such that there is a global bound on the degree of vertices and on the length of paths. We can define an equivalence relation $v \sim u$ iff there exists an automorphism $f$ of $G$ such that $f(u) = v$. Is the quotient of $G$ w.r.t. $\sim$ finite?

Answer 1

Yes.

By Konig's Lemma, if the graph $G$ has finite bounded degree $\Delta$ and finite path length $\rho$, then it must be disconnected, and each connected component must be a graph with finitely many vertices.

Further, there are only finitely many connected graphs (up to isomorphism) with maximum degree at most $\Delta$ and diameter at most $\rho$ (diameter $\leq$ max path length).

Thus every connected component of the graph is isomorphic to one of finitely many finite graphs. If two components $C_1$ and $C_2$ of $G$ are isomorphic by an isomorphism $f$, you can create an isomorphism of $G$ by fixing the rest of $G$, and using $f$ to swap the vertices of $C_1$ and $C_2$. Thus there is a collection of finitely many components of $G$ such that every vertex is equivalent to a vertex in one of these components.