Prime graph explained

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