-
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.
-