# When is the intersection of graph automorphism groups again the automorphism group of a graph?

For the purposes of this question, all graphs are undirected and contain no loops.

Fix a non-negative integer $$n$$. Then we can see the automorphism group $$\text{Aut}(G)$$ of every graph $$G$$ with vertices $$\{ 1,\dots,n \}$$ as a subgroup of the symmetric group $$S_n$$. As is known, the intersection of any two subgroups is again a subgroup. This means that, for any two graphs $$G_1$$ and $$G_2$$ on $$n$$ vertices, the intersection $$\text{Aut}(G_1) \cap \text{Aut}(G_2)$$ is also a subgroup of $$S_n$$. Under what conditions is there a graph $$G_3$$ (also on $$n$$ vertices) such that $$\text{Aut}(G_3) = \text{Aut}(G_1) \cap \text{Aut}(G_2)$$ (again, as a subgroup of $$S_n$$)?

I'm aware of Frucht's theorem, but that construction in general does not guarantee the number of vertices remains the same.

For small graphs ($$n \le 5$$), it seems the above is possible for all subgroups except the trivial subgroup.

• Indeed if $\Gamma$ is a graph such that $|\operatorname{Aut}(\Gamma)| = 1$, then $G$ has at least $6$ vertices. But also, if $\Gamma$ is a graph such that $|\operatorname{Aut}(\Gamma)| = 3$, then $G$ has at least $9$ vertices. See for example here. – spin Jan 17 at 19:34

I also think your claim that this is the only exception for $$n\leq 5$$ is false.
For example, for $$n=4$$, the Sylow $$2$$-subgroups are automorphism groups of graphs ($$4$$-cycles, for example) but if you intersect these, you get the normal subgroup of $$S_4$$ consisting of the identity and the double transposition. (Isomorphic to the Klein group.) This is not the automorphism group of a graph, as can easily be checked by hand. (The only graphs it preserves are the complete graph or a $$4$$-cycle or complements of these, so the full group is always bigger.)