Edge Transitive Graph

• A graph is edge transitive if its automorphism group acts transitively on .

• (Godsil 3.2.1) Let be an edge-transitive graph with no isolated vertices. If is not vertex transitive, then has exactly two orbits and these two orbits form a bipartition of . That is all edge transitive graphs that are not vertex transitive are bipartite. ¹

  • Proof: For any edge there will be an automorphism mapping an edge incident to to . Here, either or under the automorphism but not both. Thus, are part of different orbits.

    No automorphism maps , where lie in the same orbit, to above. Hence the two orbits form a bipartition.

Links §

• Algebraic Graph Theory by Godsil and Royle

Footnotes §

1. Note how (Godsil 3.2.1) and (Godsil 3.2.2) Deal with bipartite and Eulerian graphs. Both are edge transitive but one is vertex transitive while the other not. See graph and matroid duality for more on this. ↩