The Cost of Symmetry in Connected Graphs

We answer a question posed in a joint paper by Klyachko and Luneva about the optimality of an estimate for the cost of symmetry in graphs. The original estimate is that if one can delete $n$ vertices from a connected graph $G$ so that the resulting graph contains no connected subgraph isomorphic to $\Gamma$, then in $G$ there exists a vertex subset of cardinality $\le n|V(\Gamma)|$ invariant under all automorphisms of $G$ such that the graph obtained from $G$ by deleting this subset contains no subgraph isomorphic to $\Gamma$. We prove that there exists a graph $\Gamma$ for which this estimate is not optimal.