Editing Petersen graph (section)

== Other properties ==
The Petersen graph:
* is 3-connected and hence 3-edge-connected and bridgeless. See the [[Glossary of graph theory#Connectivity|glossary]].
* has independence number 4 and is 3-partite. See the [[Glossary of graph theory#Independence|glossary]].
* is [[cubic graph|cubic]], has [[domination number]] 3, and has a [[perfect matching]] and a [[2-factor]].
* has 6 distinct perfect matchings.
* is the smallest cubic graph of [[girth (graph theory)|girth]] 5. (It is the unique <math>(3,5)</math>-[[cage (graph theory)|cage]]. In fact, since it has only 10 vertices, it is the unique <math>(3,5)</math>-[[Moore graph]].)<ref name="hs60">{{citation | author1-link = Alan Hoffman (mathematician) | last1 = Hoffman | first1 = Alan J. | last2 = Singleton | first2 = Robert R.
 | title = Moore graphs with diameter 2 and 3
 | journal = IBM Journal of Research and Development
 | volume = 5
 | issue = 4
 | year = 1960
 | pages = 497–504
 | url = http://www.research.ibm.com/journal/rd/045/ibmrd0405H.pdf
 |mr=0140437
 | doi=10.1147/rd.45.0497}}.</ref>
* every cubic bridgeless graph without Petersen minor has a cycle double cover.<ref>{{citation | author1-link = Brian Alspach (mathematician) | last1 = Alspach | first1 = Brian | last2 = Zhang | first2 = Cun-Quan
| title = Cycle covers of cubic multigraphs
 | journal = Discrete Math.
 | volume = 111
| year = 1993
 | issue = 1–3 | pages = 11–17| doi = 10.1016/0012-365X(93)90135-G }}.</ref>
* is the smallest cubic graph with [[Colin de Verdière graph invariant]] μ = 5.<ref>{{citation | doi=10.1090/S0002-9939-98-04244-0 | author=László Lovász, Alexander Schrijver | title=A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs | journal=[[Proceedings of the American Mathematical Society]] | volume=126 | issue=5 | year=1998 | pages=1275–1285 | s2cid=7790459 | url=https://www.ams.org/journals/proc/1998-126-05/S0002-9939-98-04244-0/S0002-9939-98-04244-0.pdf}}</ref>
* is the smallest graph of [[cop number]] 3.<ref>{{citation
 | last1 = Baird | first1 = William
 | last2 = Beveridge | first2 = Andrew
 | last3 = Bonato | first3 = Anthony
 | last4 = Codenotti | first4 = Paolo
 | last5 = Maurer | first5 = Aaron
 | last6 = McCauley | first6 = John
 | last7 = Valeva | first7 = Silviya
 | arxiv = 1308.2841
 | issue = 1
 | journal = Contributions to Discrete Mathematics
 | mr = 3265753
 | pages = 70–84
 | title = On the minimum order of {{mvar|k}}-cop-win graphs
 | url = https://cdm.ucalgary.ca/article/view/62207
 | volume = 9
 | year = 2014
 | doi = 10.11575/cdm.v9i1.62207 | doi-access = free}}</ref>
*has [[radius (graph theory)|radius]] 2 and [[diameter (graph theory)|diameter]] 2. It is the largest cubic graph with diameter 2.{{efn|This follows from the fact that it is a Moore graph, since any Moore graph is the largest possible regular graph with its degree and diameter.<ref name="hs60"/>}}
* has 2000 [[Spanning tree (mathematics)|spanning tree]]s, the most of any 10-vertex cubic graph.<ref>{{Citation
 | last1 = Jakobson | first1= Dmitry | last2= Rivin | first2= Igor
 | title = On some extremal problems in graph theory
 | year = 1999
 | arxiv= math.CO/9907050| bibcode= 1999math......7050J }}
</ref><ref>{{citation| last = Valdes|first= L.| title = Extremal properties of spanning trees in cubic graphs
 | journal = Congressus Numerantium
 | year = 1991
 | volume = 85
 | pages = 143–160}}.
</ref>{{efn|The cubic graphs with 6 and 8 vertices maximizing the number of spanning trees are [[Möbius ladder]]s.}}
* has [[chromatic polynomial]] <math>t(t-1)(t-2)\left(t^7-12t^6+67t^5-230t^4+529t^3-814t^2+775t-352\right)</math>.<ref name="biggs">{{Citation | author=Biggs, Norman | title=Algebraic Graph Theory | edition=2nd | location=Cambridge | publisher=Cambridge University Press | year=1993 | isbn=0-521-45897-8}}</ref>
* has [[characteristic polynomial]] <math>(t-1)^5(t+2)^4(t-3)</math>, making it an [[integral graph]]—a graph whose [[Spectral graph theory|spectrum]] consists entirely of integers.