# 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?

• I commented on your other question too, but I shall ask here just in case. Have you done anything in this topic, or do you intend to do so? I'm hoping to work on it, but if you're doing some serious research in this, I'd prefer to do something different from what you're doing [within the same topic]. Oct 8, 2015 at 8:46
• And your conjecture is true for trees (I proved it just now). I can post the outline of the proof if you're interested [or email it to you or something]. It's not difficult to prove anyway. Oct 8, 2015 at 9:04
• I think you should post your proof as an answer to this question, or you can also mail me at: kozerenkosergiy@ukr.net. Oct 15, 2015 at 9:57

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 @}
]