Prime graph

This article is about graphs defined from finite groups. For the graphs that cannot be decomposed as a product of smaller graphs, see Cartesian product of graphs.

In the mathematics of graph theory and finite groups, a prime graph is an undirected graph defined from a group. These graphs were introduced in a 1981 paper by J. S. Williams, credited to unpublished work from 1975 by K. W. Gruenberg and O. Kegel.

Definition

The prime graph of a group has a vertex for each prime number that divides the order (number of elements) of the given group, and an edge connecting each pair of prime numbers $p$ and $q$ for which there exists a group element with order $pq$.

Equivalently, there is an edge from $p$ to $q$ whenever the given group contains commuting elements of order $p$ and of order $q$, or whenever the given group contains a cyclic group of order $pq$ as one of its subgroups.

Properties

Certain finite simple groups can be recognized by the degrees of the vertices in their prime graphs. The connected components of a prime graph have diameter at most five, and at most three for solvable groups. When a prime graph is a tree, it has at most eight vertices, and at most four for solvable groups.

Related graphs

Variations of prime graphs that replace the existence of a cyclic subgroup of order $pq$, in the definition for adjacency in a prime graph, by the existence of a subgroup of another type, have also been studied. Similar results have also been obtained from a related family of graphs, obtained from a finite group through the degrees of its characters rather than through the orders of its elements.