4
$\begingroup$

I am reading "Algebraic Graph Theory" by Norman Biggs (1974). On page 119, there is a proposition which says the following:

Proposition 18.1: Let $[\alpha]$ be a $t$-arc in a cubic $t$-transitive graph $X$. Then an automorphism of $X$ which fixes $[\alpha]$ must be the identity automorphism.

To understand the Proposition, and the proof, some definitions and lemmas are needed. A $t$-arc is defined as follows:

A $t$-arc in a graph $X$ is an ordered set $[\alpha] = (\alpha_0,\ldots, \alpha_t)$ of $t+1$ vertices in $V(X)$, such that $\alpha_i \alpha_{i+1} \in E(X)$ and $\alpha_{i-1} \neq \alpha_{i+1}$ for $1 \leq i \leq t-1$.

We can concatenate such arcs by the following definition

If $[\alpha]$ is a $t$-arc in a graph $X$ and $[\beta]$ is a $s$-arc in $X$, then we use $[\alpha . \beta]$ to denote the $(t+s+1)$-arc $(\alpha_0,\ldots,\alpha_t,\beta_0,\ldots,\beta_s)$, provided that $\alpha_t \beta_0 \in E(X)$, $\alpha_{t-1} \neq \beta_0$ and $\alpha_{t} \neq \beta_1$.

We also need the term succesive arcs

Let $[\alpha]$ and $[\beta]$ be any two $s$-arcs in a graph $X$. We say that $[\beta]$ is a successor of $[\alpha]$ if $\beta_i = \alpha_{i+1}$ $(0 \leq i \leq s-1)$.

We also need a Lemma which states

Lemma 17.4: Let $X$ be a connected graph in which the degree of each vertex is at least three. If $s \geq 1$ and $[\alpha],[\beta]$ are any two $s$-arcs in $X$, then there is a finite sequence $[\alpha^{(i)}]$ $(1 \leq i \leq l)$ of $s$-arcs in $X$ such that $[\alpha^{(1)}] = [\alpha]$, and $[\alpha^{(l)}] = [\beta]$, and $[\alpha^{(i+1)}]$ is a successor of $[\alpha^{(i)}]$ for $1 \leq i \leq s-1$.

and at last a Theorem which says

Theorem 17.5: Let $X$ be a connected graph, where all vertices in $V(X)$ are at least 3 and let $[\alpha]$ be a $t$-arc in $X$. Suppose the vertices adjacent to $\alpha_t$ are $\alpha_{t-1}$ and $v_1,v_2,\ldots,v_l$, and let $[\beta^{(i)}]$ denote the $t$-arc $(\alpha_1,\alpha_2,\ldots,\alpha_t,v_i)$ for $1 \leq i \leq l$, so that each $[\beta^{(i)}]$ is a successor of $[\alpha]$. Now $Aut(X)$ is transitive on $t$-arcs if and only if there are automorphisms $g_1,g_2,\ldots,g_l$ in $Aut(X)$ such that $g_i[\alpha] = [\beta^{(i)}] (1 \leq i \leq l)$.

The proof of the proposition goes as follows:

Proof of Proposition 18.1: Suppose $f$ is an automorphism fixing $\alpha_0,\alpha_1,\ldots,\alpha_t$; if $f$is not the identity, then $f$ does not fix all $t$-arcs in $X$. Thus, it follows from Lemma 17.4 that there is some $t$-arc $[\beta]$ such that $f$ fixes $[\beta]$, but $f$ does not fix both successors of $[\beta]$. In fact, if $\beta_{t-1},u_1,u_2$ are the vertices adjacent to $\beta_t$, then $f$ must interchange $u_1$ and $u_2$. Let $w \neq \beta_1$ be a vertex adjacent to $\beta_0$. Since $X$ is $t$-transitive there is an automorphism $h \in Aut(X)$ taking the $t$-arc $(w,\beta_0,\ldots,\beta_{t-1})$ to $[\beta]$, and we may suppose the notation chosen so that $h(\beta_t) = u_1$. Then $h$ and $fh$ are automorphisms of $X$ taking the $(t+1)$-arc $[w.\beta]$ to its two successors, and by Theorem 17.5, $Aut(X)$ is transitive on $(t+1)$-arcs. This contradicts our hypothesis, and so we must have $f = 1$.

I have some problem understanding parts of the proof. The first thing, which is not really essential for proving the proposition, is the part:

In fact, if $\beta_{t-1},u_1,u_2$ are the vertices adjacent to $\beta_t$, then $f$ must interchange $u_1$ and $u_2$

The other problem, which is quite essential to the proof, is the part:

Since $X$ is $t$-transitive there is an automorphism $h \in Aut(X)$ taking the $t$-arc $(w,\beta_0,\ldots,\beta_{t-1})$ to $[\beta]$, and we may suppose the notation chosen so that $h(\beta_t) = u_1$. Then $h$ and $fh$ are automorphisms of $X$ taking the $(t+1)$-arc $[w.\beta]$ to its two successors

I get why there must be such a $h$, taking $(w,\beta_0,\ldots,\beta_{t-1})$ to $[\beta]$. But I do not get, why we can (without loss of generality) assume that $h(\beta_t)$ is a neighbor of $\beta_t$. Thus, I do not see how the other part; that

$h$ and $fh$ are automorphisms of $X$ taking the $(t+1)$-arc $[w.\beta]$ to its two successors

is true.

This question has become rather long, and I have surely missed a definition of something. Everything in gray, can be found in Biggs 1974, on pages 112-115. I have understood the proof of Theorem 17.5, but the proof of Proposition 18.1 uses some arguments, which are non-obvious to me.

1 Answers 1

1

In the end, I found the missing argument. It is a rather simple one, but I did not see it at first. In fact, both of the questions I raised about the proof, needed the same argument, and I found out, that the statement:

In fact, if $\beta_{t-1},u_1,u_2$ are the vertices adjacent to $\beta_t$, then $f$ must interchange $u_1$ and $u_2$

is essential to the proof. The reason that the above statement is correct, is that an automorphism on a graph, preserves neighbors. That is, for a graph $X$; then if $v,u \in V(X)$ are neighbors, and $\pi$ is an automorphism on $X$, then $\pi(v),\pi(u)$ are also neighbors.

Using this knowledge of automorphisms on graphs, we can see, that if $f$ fixes $\beta_t$, but does not fix both of the successors of $[\beta]$ $u_1$ and $u_2$, then $f$ has to interchange $u_1$ and $u_2$ to preserve the neighborhood of $\beta_t$.

The same argument applies for the part:

Since $X$ is $t$-transitive there is an automorphism $h \in Aut(X)$ taking the $t$-arc $(w,\beta_0,\ldots,\beta_{t-1})$ to $[\beta]$, and we may suppose the notation chosen so that $h(\beta_t) = u_1$. Then $h$ and $fh$ are automorphisms of $X$ taking the $(t+1)$-arc $[w.\beta]$ to its two successors

since we now know that $u_1$ is a neighbor of $\beta_t$, even after applying $h$.