Editing Petersen graph (section)

{{Short description|Cubic graph with 10 vertices and 15 edges}}
{{Infobox graph
 | name = Petersen graph
 | image = Petersen1 tiny.svg
 | image_size = 200px
 | image_caption = The Petersen graph is most commonly drawn as a pentagon with a pentagram inside, with five spokes.
 | namesake = [[Julius Petersen]]
 | vertices = 10
 | edges = 15
 | automorphisms = 120 (S<sub>5</sub>)
 | radius = 2
 | diameter = 2
 | girth = 5
 | chromatic_number = 3
 | chromatic_index = 4
 | fractional_chromatic_index = 3
 | genus = 1
 | properties = [[Cubic graph|Cubic]]<br/>[[Strongly regular graph|Strongly regular]]<br/>[[Distance-transitive graph|Distance-transitive]]<br/>[[Snark (graph theory)|Snark]]
}}
{{unsolved|mathematics|'''Conjecture:''' Every [[bridge (graph theory)|bridgeless graph]] has a cycle-continuous mapping to the Petersen graph.}}

In the [[mathematics|mathematical]] field of [[graph theory]], the '''Petersen graph''' is an [[undirected graph]] with 10 [[vertex (graph theory)|vertices]] and 15 [[edge (graph theory)|edge]]s. It is a small graph that serves as a useful example and [[counterexample]] for many problems in graph theory. The Petersen graph is named after [[Julius Petersen]], who in 1898 constructed it to be the smallest [[bridge (graph theory)|bridge]]less [[cubic graph]] with no three-[[edge coloring|edge-coloring]].<ref>{{citation|url=http://www.win.tue.nl/~aeb/drg/graphs/Petersen.html|title=The Petersen graph|first=Andries E.|last=Brouwer|author-link=Andries Brouwer}}</ref><ref>{{citation|first=Julius|last=Petersen|author-link=Julius Petersen|title=Sur le théorème de Tait|journal=[[L'Intermédiaire des Mathématiciens]]|volume=5|year=1898|pages=225&ndash;227|url=https://archive.org/details/lintermdiairede03lemogoog/page/n239/mode/1up?view=theater}}</ref>

Although the graph is generally credited to Petersen, it had in fact first appeared 12 years earlier, in a paper by {{harvs|first=A. B.| last=Kempe |authorlink=Alfred Kempe|year=1886|txt}}. Kempe observed that its vertices can represent the ten lines of the [[Desargues configuration]], and its edges represent pairs of lines that do not meet at one of the ten points of the configuration.<ref>{{citation|first=A. B.|last=Kempe|title=A memoir on the theory of mathematical form|journal=Philosophical Transactions of the Royal Society of London|volume=177|pages=1&ndash;70|year=1886|doi=10.1098/rstl.1886.0002|s2cid=108716533 }}</ref>

[[Donald Knuth]] states that the Petersen graph is "a remarkable configuration that serves as a counterexample to many optimistic predictions about what might be true for graphs in general."<ref>{{citation|first=Donald E.|last=Knuth|title=The Art of Computer Programming; volume 4, pre-fascicle 0A. A draft of section 7: Introduction to combinatorial searching}}</ref>

The Petersen graph also makes an appearance in [[tropical geometry]]. The cone over the Petersen graph is naturally identified with the moduli space of five-pointed rational tropical curves.