Skip to main content
1 of 3

Automorphism group action leads to a "quotient graph"

Let $G$ be a simple graph. Consider the natural equivalence relation $\sim$ on $V(G)$:

$u\sim v$ iff there exists and automorphism $\phi\in Aut(G)$, such that $\phi(u)=v$.

Define a new graph $G_{Aut}$ with $V(G_{Aut})=G/{\sim}$ and there exists an edge $A-B$, for $A,B\in G/{\sim}$ iff there exists $a\in A$ and $b\in B$, such that $ab\in E(G)$.

Note, that if $G$ has trivial automorphism group, then $G_{Aut}\simeq G$. Similarly, if $G$ is vertex-transitive, then $G_{Aut}\simeq K_{1}$.

Question 1: Does for every $G$ there exists $H$ with $H_{Aut}\simeq G\ ?$ (I think the answer is YES)

Question 2: If so, how many vertices $H$ must have?