# Embedding of a “quotient graph”

Consider the simple undirected graph $G$ with natural equivalence relation $\sim$ on $V(G)$:

$u\sim v$ iff they are similar, i.e. iff there exists $\phi\in Aut(G)$ with $\phi(u)=v$.

Define a "quotient graph" $G_{Aut}$ in the following way:

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

Conjecture: If in $G$ every pair of similar vertices are non-adjacent, then $G_{Aut}\subset G \ ?$

ADDED: As Anton showed, this conjecture is false. But what one can said if $G$ is a tree? Does conjecture remains false?

-

No. Here is a simple counterexample:

-

The following seems to be a counterexample, verified by a Magma calcualtion. The vertex set is $\{1,2,\ldots,16\}$ and the edge set is $E$. The quotient graph is the complete graph on four vertices and has $S_4$ as automorphism group, but $|{\rm Aut}(G)|=4$.

> E:={
{1,5}, {2,6}, {3,7},{4,8},

{1,9}, {1,10}, {1,11}, {1,12},
{2,9}, {2,10}, {2,11}, {2,12},
{3,9}, {3,10}, {3,11}, {3,12},
{4,9}, {4,10}, {4,11}, {4,12},

{1,14}, {1,15}, {1,16},
{2,13}, {2,15}, {2,16},
{3,13}, {3,14}, {3,16},
{4,13}, {4,14}, {4,15},

{5,9}, {5,10}, {6,10}, {6,11}, {7,11}, {7,12}, {8,12}, {8,9},

{5,13}, {5,14}, {6,14}, {6,15}, {7,15}, {7,16}, {8,16}, {8,13},

{9,13}, {10,14}, {11,15}, {12,16} };

> G:=Graph<16|E>;
> A:=AutomorphismGroup(G);
> Order(A);
4
> Orbits(A);
[
GSet{@ 1, 2, 3, 4 @},
GSet{@ 5, 6, 7, 8 @},
GSet{@ 9, 10, 11, 12 @},
GSet{@ 13, 14, 15, 16 @}
]

-