Given two simple connected graphs $G$ and $H$, given that their automorphism groups are non-trivial, is it necessary that if $\text{Aut}(G)$ is a subgroup of $\text{Aut}(H)$, then there exists a subgraph $H'\subseteq H$ such that $\text{Aut}(G)\cong\text{Aut}(H')$?
If the answer is no, could I see a counter example, and is there then a sufficient constraint on $G$ and $H$ which does make this true?
If the answer is yes and the proof isn't absolutely monsterous, I'd love a hint towards trying to prove it myself.
Let $G$ be the $9$-vertex graph with automorphism group $C_3$, shown below. Let $H$ be $K_3$, with automorphism group $S_3$.
Then $\text{Aut}(G)$ is a subgroup of $\text{Aut}(H)$, but there's no subgraph of $H$ whose automorphism group is $C_3$. In fact, $G$ is the smallest graph whose automorphism group is $C_3$.
This generalizes to a whole class of counterexamples, where $H$ is a cycle graph. In that case, $\text{Aut}(H)$ is a dihedral group, but there is no subgraph of $H$ whose automorphism group is the corresponding cyclic group.