23

Let $G(V,E)$ be an undirected graph, potentially with loops and multi-edges. Assume the following two properties hold:

  1. $\forall a \in V, \exists f \in \operatorname{Aut}(G), f(a) \ne a$
  2. $\forall f\in \operatorname{Aut}(G), \exists a \in V, f(a) = a $

Prove: $10 \le |V| $

kabenyuk
  • 10,712
kotomord
  • 1,814
  • I know a small brute-force solution, but want to find more eligible – kotomord Mar 29 '17 at 23:53
  • 4
    Do you know an example of a graph having those two properties? – bof Oct 11 '20 at 00:25
  • It seems to be a NP problem not easy to solve and brute force might be the only option: https://math.stackexchange.com/questions/213716/number-of-automorphisms-of-a-given-graph –  Sep 29 '21 at 16:03

0 Answers0