{{short description|Undirected graph defined from a group}} {{about|graphs defined from finite groups|other uses|Glossary of graph theory#prime}}
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 Karl W. Gruenberg and Otto H. Kegel.{{r|williams}}
==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 <math>p</math> and <math>q</math> for which there exists a group element with order <math>pq</math>.{{r|williams|cyclic}}
Equivalently, there is an edge from <math>p</math> to <math>q</math> whenever the given group contains commuting elements of order <math>p</math> and of order <math>q</math>,{{r|williams}} or whenever the given group contains a cyclic group of order <math>pq</math> as one of its subgroups.{{r|cyclic}}
==Properties== Certain finite simple groups can be recognized by the degrees of the vertices in their prime graphs.{{r|degrees}} The connected components of a prime graph have diameter at most five, and at most three for solvable groups.{{r|diam}} When a prime graph is a tree, it has at most eight vertices, and at most four for solvable groups.{{r|tree}}
==Related graphs== Variations of prime graphs that replace the existence of a cyclic subgroup of order <math>pq</math>, in the definition for adjacency in a prime graph, by the existence of a subgroup of another type, have also been studied.{{r|cyclic}} 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.{{r|character}}
==References== <references>
<ref name=cyclic>{{citation | last1 = Abe | first1 = Seiichi | last2 = Iiyori | first2 = Nobuo | doi = 10.14492/hokmj/1350912979 | issue = 2 | journal = Hokkaido Mathematical Journal | mr = 1776716 | pages = 391–407 | title = A generalization of prime graphs of finite groups | volume = 29 | year = 2000| url = http://projecteuclid.org/euclid.hokmj/1350912979 }}</ref>
<ref name=character>{{citation | last = Tong-Viet | first = Hung P. | doi = 10.1016/j.jalgebra.2012.12.024 | journal = Journal of Algebra | mr = 3017021 | pages = 196–206 | title = Groups whose prime graphs have no triangles | volume = 378 | year = 2013| s2cid = 119118934 | arxiv = 1303.3457 }}</ref>
<ref name=degrees>{{citation | last1 = Moghaddamfar | first1 = A. R. | last2 = Zokayi | first2 = A. R. | last3 = Darafsheh | first3 = M. R. | doi = 10.1142/S1005386705000398 | issue = 3 | journal = Algebra Colloquium | mr = 2144997 | pages = 431–442 | title = A characterization of finite simple groups by the degrees of vertices of their prime graphs | volume = 12 | year = 2005}}</ref>
<ref name=diam>{{citation | last = Lucido | first = Maria Silvia | author-link = Maria Silvia Lucido | doi = 10.1515/jgth.1999.011 | issue = 2 | journal = Journal of Group Theory | mr = 1681526 | pages = 157–172 | title = The diameter of the prime graph of a finite group | volume = 2 | year = 1999 | zbl = 0921.20020}}</ref>
<ref name=tree>{{citation | last = Lucido | first = Maria Silvia | author-link = Maria Silvia Lucido | issue = 1 | journal = Bollettino della Unione Matematica Italiana | mr = 1881928 | pages = 131–148 | title = Groups in which the prime graph is a tree | volume = 5 | year = 2002 | zbl = 1097.20022}}</ref>
<ref name=williams>{{citation | last = Williams | first = J. S. | doi = 10.1016/0021-8693(81)90218-0 | issue = 2 | journal = Journal of Algebra | mr = 617092 | pages = 487–513 | title = Prime graph components of finite groups | volume = 69 | year = 1981| doi-access = free }}</ref>
</references>
Category:Application-specific graphs Category:Finite groups