Edge-transitive graph

Graph families defined by their automorphisms
distance-transitive	$\rightarrow$	distance-regular	$\leftarrow$	strongly regular
$\downarrow$
symmetric (arc-transitive)	$\leftarrow$	t-transitive, t ≥ 2
$\downarrow$(if connected)
vertex- and edge-transitive	$\rightarrow$	edge-transitive and regular	$\rightarrow$	edge-transitive
$\downarrow$		$\downarrow$
vertex-transitive	$\rightarrow$	regular
$\uparrow$
Cayley graph		skew-symmetric		asymmetric

This article is about graph theory. For edge transitivity in geometry, see Edge-transitive.

In the mathematical field of graph theory, an edge-transitive graph is a graph G such that, given any two edges e₁ and e₂ of G, there is an automorphism of G that maps e₁ to e₂.

In other words, a graph is edge-transitive if its automorphism group acts transitively upon its edges.

Examples and properties

The Gray graph is edge-transitive and regular, but not vertex-transitive.

Edge-transitive graphs include any complete bipartite graph $K_{m,n}$, and any symmetric graph, such as the vertices and edges of the cube. Symmetric graphs are also vertex-transitive (if they are connected), but in general edge-transitive graphs need not be vertex-transitive. The Gray graph is an example of a graph which is edge-transitive but not vertex-transitive. All such graphs are bipartite, and hence can be colored with only two colors.

An edge-transitive graph that is also regular, but not vertex-transitive, is called semi-symmetric. The Gray graph again provides an example.

See also

• Edge-transitive (in geometry)

External links

• Weisstein, Eric W., "Edge-transitive graph" from MathWorld.