  We prove that, if $\Gamma$ is a finite connected $3$-valent
vertex-transitive, or $4$-valent vertex- and edge-transitive graph, then either
$\Gamma$ is part of a well-understood family of graphs, or every non-identity
automorphism of $\Gamma$ fixes at most $1/3$ of the edges. This answers a
question proposed by Primo\v{z} Poto\v{c}nik and the third author.
