is edge-transitive and
regular, but not
vertex-transitive. The number of connected simple edge-transitive graphs on n vertices is 1, 1, 2, 3, 4, 6, 5, 8, 9, 13, 7, 19, 10, 16, 25, 26, 12, 28 ... Edge-transitive graphs include all
symmetric graphs, such as the vertices and edges of the
cube. Examples of edge but not vertex transitive graphs include the
complete bipartite graphs K_{m,n} where m ≠ n, which includes the star graphs K_{1,n}. For graphs on n vertices, there are (n-1)/2 such graphs for odd n and (n-2) for even n. Additional edge transitive graphs which are not symmetric can be formed as subgraphs of these complete bi-partite graphs in certain cases. Subgraphs of complete bipartite graphs Km,n exist when m and n share a factor greater than 2. When the greatest common factor is 2, subgraphs exist when 2n/m is even or if m=4 and n is an odd multiple of 6. So edge transitive subgraphs exist for K3,6, K4,6 and K5,10 but not K4,10. An alternative construction for some edge transitive graphs is to add vertices to the midpoints of edges of a symmetric graph with v vertices and e edges, creating a bipartite graph with e vertices of order 2, and v of order 2e/v. An edge-transitive graph that is also
regular, but still not vertex-transitive, is called
semi-symmetric. The
Gray graph, a cubic graph on 54 vertices, is an example of a regular graph which is edge-transitive but not vertex-transitive. The
Folkman graph, a quartic graph on 20 vertices is the smallest such graph. The
vertex connectivity of an edge-transitive graph always equals its
minimum degree. == See also ==