Graful lui Petersen

	Graful lui Petersen
	; Graful lui Petersen este cel mai adesea desenat ca un pentagon cu o pentagramă în interior, cu cince spițe.
Numit după	Julius Petersen
Noduri	10
Muchii	15
Rază	2
Diametru	2
Grosime	5
Automorfisme	120 (S5)
Număr cromatic	3
Index cromatic	4
Index cromatic fracționar	3
Gen	1
Proprietăți	Cubic; Tare regulat; Distanță-tranzitiv; Snark

Acest articol participă la Concursul de scriere. Ajutați la îmbunătățirea lui!

În domeniul matematic al teoriei grafurilor, graful lui Petersen este un graf neorientat cu 10 noduri și 15 muchii. Este un graf mic care servește drept exemplu și contraexemplu util pentru multe probleme din teoria grafurilor. Graful lui Petersen este numit după Julius Petersen, care în 1898 l-a construit în așa fel încât să fie cel mai mic graf cubic fără punți care nu are 3-colorări de muchii.^[1]^[2]

Deși graful este în general creditat lui Petersen, de fapt a apărut pentru prima dată cu 12 ani mai devreme, într-o lucrare a lui A. B. Kempe (1886). Kempe a observat că nodurile sale pot reprezenta cele zece linii ale configurației lui Desargues, iar muchiile sale reprezintă perechi de linii care nu se întâlnesc într-unul dintre cele zece puncte ale configurației.^[3]

Donald Knuth afirmă că graful lui Petersen este „o configurație remarcabilă care servește ca un contraexemplu pentru multe predicții optimiste despre ceea ce ar putea fi adevărat pentru grafuri în general”.^[4]

Graful lui Petersen apare, de asemenea, în geometria tropicală. Conul de deasupra grafului lui Petersen este identificat în mod natural cu spațiul de module al curbelor tropicale raționale 5-punctate.

Construcții

Graful lui Petersen ca graf Kneser

KG_{5,2}

Graful lui Petersen este complementul grafului linie al lui $K_{5}$ . Este de asemenea graful Kneser $KG_{5,2}$ ; aceasta înseamnă că are un nod pentru fiecare submulțime cu 2 elemente a unei mulțimi cu 5 elemente, iar două noduri sunt conectate printr-o muchie dacă și numai dacă submulțimile corespunzătoare cu 2 elemente sunt disjuncte. Fiind un graf Kneser de forma $KG_{2n-1,n-1}$ , este un exemplu de graf impar.

Din punct de vedere geometric, graful lui Petersen este graful format din nodurile și muchiile semi-dodecaedrului, adică un dodecaedru cu punctele, liniile și fețele opuse identificate împreună.

Scufundări

Graful lui Petersen este neplanar. Orice graf neplanar are ca minori graful complet $K_{5}$ sau graful bipartit complet $K_{3,3}$ , iar graful lui Petersen le are pe amândouă. Minorul $K_{5}$ poate fi format prin contractarea muchiilor unui cuplaj perfect, de exemplu cele cinci muchii scurte din prima imagine. Minorul $K_{3,3}$ poate fi format prin ștergerea unui nod (de exemplu nodul central al desenului 3-simetric) și contractarea unei muchii incidente la fiecare vecin al nodului șters.

Graful lui Petersen are numărul de încrucișare 2 și este 1-planar.

Cel mai comun și simetric desen plan al grafului lui Petersen, ca pentagramă într-un pentagon, are cinci încrucișări. Totuși, acesta nu este cel mai bun desen pentru minimizarea încrucișărilor; există alt desen (prezentat în figură) cu doar două încrucișări. Deoarece este neplanar, are cel puțin o încrucișare în orice desen, iar dacă o muchie încrucișată este îndepărtată din orice desen, rămâne neplanar și are o altă încrucișare; prin urmare, numărul său de încrucișare este exact 2. Fiecare muchie din acest desen este încrucișată cel mult o dată, deci graful lui Petersen este 1-planar. Pe un tor graful lui Petersen poate fi desenat fără încrucișări de muchii; are prin urmare genul orientabil 1.

Graful lui Petersen este un graf cu distanțe unu: poate fi desenat în plan, fiecare muchie având lungimea unu.

De asemenea, graful lui Petersen poate fi desenat (cu încrucișări) în plan în așa fel încât toate muchiile să aibă lungime egală. Adică este un graf cu distanțe unu.

Cea mai simplă suprafață neorientabilă în care poate fi scufundat graful lui Petersen fără încrucișări este planul proiectiv. Aceasta este scufundarea dată de construcția semi-dodecaedrului grafului lui Petersen (prezentat în figură). Scufundarea în planul proiectiv mai poate fi formată din desenul pentagonal standard al grafului lui Petersen prin plasarea unui capac încrucișat în cadrul stelei cu cinci puncte în centrul desenului și direcționarea muchiilor stelei prin acest capac încrucișat; desenul rezultat are șase fețe pentagonale. Această construcție formează o aplicație regulată și arată că graful lui Petersen are genul 1 neorientabil.

Graful lui Petersen și aplicația asociată scufundate în planul proiectiv. Punctele opuse de pe cerc sunt identificate, rezultând o suprafață închisă neorientabilă de gen 1.

Simetrii

Graful lui Petersen este tare regulat (cu signatura srg(10,3,0,1)). Este de asemenea simetric, adică este muchie-tranzitiv și nod-tranzitiv. Mai mult, este 3-arc-tranzitiv: orice drum orientat din trei muchii în graful lui Petersen poate fi transformat în orice alt astfel de drum printr-o simetrie a grafului.^[5] Este unul dintre cele 13 grafuri cubice distanță-regulate.^[6]

Grupul de automorfisme al grafului lui Petersen este grupul simetric $S_{5}$ ; actiunea lui $S_{5}$ pe graful lui Petersen rezultă din construcția sa ca graf Kneser. Graful lui Petersen este un nucleu: orice morfism de la grafului lui Petersen la el însuși este un automorfism.^[7] După cum se vede în figuri, desenele grafului lui Petersen pot prezenta simetrie în cinci sau trei sensuri, dar nu este posibilă desenarea grafului lui Petersen în plan în așa fel încât desenul să prezinte grupul de simetrie complet al grafului.

În ciuda gradului său ridicat de simetrie, graful lui Petersen nu este un graf Cayley. Este cel mai mic graf nod-tranzitiv care nu este un graf Cayley.^[a]

Drumuri și cicluri hamiltoniene

Graful lui Petersen este hipo-Hamiltonian: prin ștergerea oricărui nod, cum ar fi nodul central din desen, graful rămas este hamiltonian. Acest desen cu simetrie de ordin 3 este cel dat de Kempe (1886).

Graful lui Petersen are un drum hamiltonian, dar nu are cicluri hamiltoniene. Este cel mai mic graf cubic fără punți, fără cicluri hamiltoniene. Este hipohamiltonian, ceea ce înseamnă că, deși nu are niciun ciclu hamiltonian, ștergerea oricărui nod îl face hamiltonian și este cel mai mic graf hipohamiltonian.

Fiind un graf nod-tranzitiv conex finit care nu are niciun ciclu hamiltonian, graful lui Petersen este un contraexemplu pentru o variantă a conjecturii lui Lovász, dar formularea canonică a conjecturii cere un drum hamiltonian și este verificată de graful lui Petersen.

Sunt cunoscute doar cinci grafuri nod-tranzitive conexe fără cicluri hamiltoniene: graful complet K₂, graful lui Petersen, graful lui Coxeter și două grafuri derivate din grafurile lui Petersen și Coxeter prin înlocuirea fiecărui nod cu un triunghi.^[6] Dacă G este un graf 2-conex, r-regulat cu cel mult 3r + 1 noduri, atunci G este hamiltonian sau este graful lui Petersen.^[8]

Pentru a vedea că graful lui Petersen nu are niciun ciclu hamiltonian, se consideră muchiile din tăietura care deconectează 5-ciclul interior de cel exterior. Dacă există un ciclu hamiltonian C, acesta trebuie să conțină un număr par din aceste muchii. Dacă conține doar două dintre ele, nodurile lor trebuie să fie adiacente în cele două 5-cicluri, ceea ce nu este posibil. Prin urmare, conține exact patru dintre ele. Să presupunem că muchia superioară a tăieturii nu este conținută în C (toate celelalte cazuri sunt identice prin simetrie). Dintre cele cinci muchii din ciclul exterior, cele două muchii superioare trebuie să fie în C, cele două muchii laterale trebuie să nu fie în C, prin urmare, muchia inferioară trebuie să fie în C. Cele două muchii de sus din ciclul interior trebuie să fie în C, dar acest lucru completează un ciclu care nu este de acoperire, care nu poate face parte dintr-un ciclu hamiltonian. Alternativ, putem de asemenea descrie grafurile 3-regulate cu 10 noduri care au un ciclu hamiltonian și să arătăm că niciunul dintre ele nu este graful lui Petersen, găsind în fiecare dintre ele un ciclu mai scurt decât orice ciclu din graful lui Petersen. Orice graf 3-regulat hamiltonian cu 10 noduri constă dintr-un ciclu C cu 10 noduri plus 5 coarde. Dacă orice coardă unește două noduri la distanța 2 sau 3 de-a lungul lui C, graful are un ciclu de 3 sau 4 cicluri și, prin urmare, nu poate fi graful lui Petersen. Dacă două coarde unesc noduri opuse ale lui C de noduri la distanța 4 de-a lungul lui C, există din nou un 4-ciclu. Singurul caz rămas este o scară Möbius formată prin unirea fiecărei perechi de noduri opuse printr-o coardă, care are din nou un 4-ciclu. Deoarece graful lui Petersen are grosimea 5, nu poate fi format în acest fel și nu are ciclu hamiltonian.

Colorare

O 4-colorare a muchiilor grafului lui Petersen

O 3-colorare a nodurilor grafului lui Petersen

Graful lui Petersen are numărul cromatic 3, ceea ce înseamnă că nodurile sale pot fi colorate cu trei culori – dar nu cu două – astfel încât nicio muchie să nu unească noduri de aceeași culoare. Are o colorare de listă cu 3 culori, conform teoremei lui Brooks pentru colorări de liste.

Graful lui Petersen are indicele cromatic 4; colorarea marginilor necesită patru culori. Fiind un graf cubic fără punți și conex cu indice cromatic 4, graful lui Petersen este un snark. Este cel mai mic snark posibil și a fost singurul snark cunoscut din 1898 până în 1946. Teorema snarkurilor, un rezultat conjecturat de W. T. Tutte și anunțat în 2001 de Robertson, Sanders, Seymour și Thomas,^[9] afirmă că fiecare snark are graful lui Petersen ca minor.

În plus, graful are indicele cromatic fracționar 3, demonstrând că diferența dintre indicele cromatic și indicele cromatic fracționar poate fi 1. Conjectura Goldberg-Seymour afirmă că acesta este cea mai mare diferență posibilă.

Numărul Thue (o variantă a indexului cromatic) al grafului lui Petersen este 5.

Graful lui Petersen necesită cel puțin trei culori în orice colorare (posibil improprie) care rupe toate simetriile sale; adică numărul său distinctiv este trei. Cu excepția grafurilor complete, este singurul graf Kneser al cărui număr distinctiv nu este 2.^[10]

Alte proprietăți

Graful lui Petersen:

este 3-conex și, prin urmare, 3-muchie-conex și fără punți. A se vedea glosarul.
are numărul de independență 4 și este tripartit. A se vedea glosarul.
este cubic, are numărul de dominație 3 și are un cuplaj perfect și un 2-factor.
are 6 cuplaje perfecte distincte.
este cel mai mic graf cubic de grosime 5. (Este unica $(3,5)$ -cușcă. De fapt, din moment ce are doar 10 noduri, este unicul graf $(3,5)$ -Moore.)^[11]
orice graf cubic fără punți și fără minori Petersen are o acoperire dublă cu cicluri.^[12]
este cel mai mic graf cubic cu invariantul Colin de Verdière μ = 5.^[13]
are raza 2 și diametrul 2. Este cel mai mare graf cubic cu diametrul 2.^[b]
are 2000 de arbori de acoperire, cel mai mult din orice graf cubic cu 10 noduri.^[14]^[15]^[c]
are polinomul cromatic $t(t-1)(t-2)\left(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352\right)$ .^[16]
are polinomul caracteristic $(t-1)^{5}(t+2)^{4}(t-3)$ , făcându-l un graf integral — un graf al cărui spectru este format în întregime din numere întregi.

Conjectura de colorare a lui Petersen

Un subgraf eulerian al unui graf $G$ este un subgraf format dintr-o submulțime de muchii ale lui $G$ , atingând fiecare nod al lui $G$ de un număr par de ori. Aceste subgrafuri sunt elementele spațiului ciclu al lui $G$ și sunt numite uneori cicluri. Dacă $G$ și $H$ sunt oricare două grafuri, o funcție de la muchiile lui $G$ la muchiile lui $H$ este definită a fi ciclu-continuă dacă preimaginea fiecărui ciclu al lui $H$ este un ciclu al lui $G$ . O conjectură a lui Jaeger afirmă că orice graf fără punți are o aplicație ciclu-continuă la graful lui Petersen. Jaeger a arătat că această conjectură implică conjectura de acoperire dublă cu 5-cicluri și conjectura Berge-Fulkerson.^[17]

Grafuri înrudite

Familia Petersen.

Graful Petersen generalizat $G(n,k)$ se formează prin unirea nodurilor unui n-gon regulat la nodurile corespunzătoare ale unui poligon stea cu simbolul Schläfli {n/k}.^[18]^[19] De exemplu, în această notație, graful lui Petersen este $G(5,2)$ : poate fi format prin unirea nodurilor corespunzătoare ale unui pentagon și ale unei stele cu cinci puncte, iar muchiile din stea unesc fiecare al doilea nod. Grafurile Petersen generalizate includ, de asemenea, n-prisma $G(n,1)$ , graful lui Dürer $G(6,2)$ , graful Möbius-Kantor $G(8,3)$ , dodecaedrul $G(10,2)$ , graful lui Desargues $G(10,3)$ și graful lui Nauru $G(12,5)$ .

Familia Petersen este formată din cele șapte grafuri care pot fi formate din graful lui Petersen prin zero sau mai multe aplicări de transformări Δ-Y sau Y-Δ. Graful complet K₆ este de asemenea în familia Petersen. Aceste grafuri formează minorii interziși pentru grafurile scufundabile fără legături, grafuri care pot fi scufundate în spațiul tridimensional astfel încât oricare două cicluri să nu fie legate.^[20]

Graful lui Clebsch conține multe copii ale grafului lui Petersen ca subgrafuri induse: pentru fiecare nod v al grafului lui Clebsch, cei zece non-vecini ai lui v induc o copie a grafului lui Petersen.

Note explicative

^ Așa cum este formulat, aceasta presupune că grafurile Cayley nu trebuie să fie neapărat conexe. Unele surse impun ca grafurile Cayley să fie conexe, ceea ce face graful vid cu două noduri să fie cel mai mic graf non-Cayley nod-tranzitiv; în raport cu definiția dată de aceste surse, graful lui Petersen este cel mai mic graf nod-tranzitiv conex care nu este Cauchy.
^ Aceasta rezultă din faptul că este un graf Moore, întrucât orice graf Moore este cel mai mare graf regulat posibil cu gradul său și diametrul său.^[11]
^ Grafurile cubice cu 6 și 8 noduri care maximizează numărul de arbori de acoperire sunt scările Möbius.

Note

^ Brouwer, Andries E., The Petersen graph
^ Petersen, Julius (1898), „Sur le théorème de Tait”, L'Intermédiaire des Mathématiciens, 5, pp. 225–227
^ Kempe, A. B. (1886), „A memoir on the theory of mathematical form”, Philosophical Transactions of the Royal Society of London, 177, pp. 1–70, doi:10.1098/rstl.1886.0002
^ Knuth, Donald E., The Art of Computer Programming; volume 4, pre-fascicle 0A. A draft of section 7: Introduction to combinatorial searching
^ Babai, László (1995), „Automorphism groups, isomorphism, reconstruction”, În Graham, Ronald L.; Grötschel, Martin; Lovász, László, Handbook of Combinatorics, I, North-Holland, pp. 1447–1540, Corollary 1.8, arhivat din original la 11 iunie 2010 .
^ ^a ^b Royle, G. "Cubic Symmetric Graphs (The Foster Census)." Arhivat în 20 iulie 2008, la Wayback Machine.
^ Cameron, Peter J. (2004), „Automorphisms of graphs”, În Beineke, Lowell W.; Wilson, Robin J., Topics in Algebraic Graph Theory, Encyclopedia of Mathematics and its Applications, 102, Cambridge University Press, Cambridge, pp. 135–153, doi:10.1017/CBO9780511529993, ISBN 0-521-80197-4, MR 2125091 ; vezi în special p. 153
^ Holton, D. A.; Sheehan, J. (1993), The Petersen Graph, Cambridge University Press, p. 32, ISBN 0-521-43594-3
^ Pegg, Ed Jr. (2002), „Book Review: The Colossal Book of Mathematics” (PDF), Notices of the American Mathematical Society, 49 (9), pp. 1084–1086, Bibcode:2002ITED...49.1084A, doi:10.1109/TED.2002.1003756
^ Albertson, Michael O.; Boutin, Debra L. (2007), „Using determining sets to distinguish Kneser graphs”, Electronic Journal of Combinatorics, 14 (1), p. R20, doi:10.37236/938  , MR 2285824 .
^ ^a ^b Hoffman, Alan J.; Singleton, Robert R. (1960), „Moore graphs with diameter 2 and 3” (PDF), IBM Journal of Research and Development, 5 (4), pp. 497–504, doi:10.1147/rd.45.0497, MR 0140437 .
^ Alspach, Brian; Zhang, Cun-Quan (1993), „Cycle covers of cubic multigraphs”, Discrete Math., 111, pp. 11–17 .
^ László Lovász, Alexander Schrijver (1998), „A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs” (PDF), Proceedings of the American Mathematical Society, 126 (5), pp. 1275–1285, doi:10.1090/S0002-9939-98-04244-0
^ Jakobson, Dmitry; Rivin, Igor (1999), On some extremal problems in graph theory, arXiv:math.CO/9907050  , Bibcode:1999math......7050J
^ Valdes, L. (1991), „Extremal properties of spanning trees in cubic graphs”, Congressus Numerantium, 85, pp. 143–160 .
^ Biggs, Norman (1993), Algebraic Graph Theory (ed. 2nd), Cambridge: Cambridge University Press, ISBN 0-521-45897-8
^ DeVos, Matt; Nešetřil, Jaroslav; Raspaud, André (2007), „On edge-maps whose inverse preserves flows or tensions”, Graph theory in Paris, Trends Math., Basel: Birkhäuser, pp. 109–138, doi:10.1007/978-3-7643-7400-6_10, ISBN 978-3-7643-7228-6, MR 2279171 .
^ Coxeter, H. S. M. (1950), „Self-dual configurations and regular graphs”, Bulletin of the American Mathematical Society, 56 (5), pp. 413–455, doi:10.1090/S0002-9904-1950-09407-5  .
^ Watkins, Mark E. (1969), „A Theorem on Tait Colorings with an Application to the Generalized Petersen Graphs”, Journal of Combinatorial Theory, 6 (2), pp. 152–164, doi:10.1016/S0021-9800(69)80116-X 
^ Bailey, Rosemary A. (1997), Surveys in Combinatorics, Cambridge University Press, p. 187, ISBN 978-0-521-59840-8

Lectură suplimentară

Exoo, Geoffrey; Harary, Frank; Kabell, Jerald (1981), „The crossing numbers of some generalized Petersen graphs”, Mathematica Scandinavica, 48, pp. 184–188, doi:10.7146/math.scand.a-11910  .
Lovász, László (1993), Combinatorial Problems and Exercises (ed. 2nd), North-Holland, ISBN 0-444-81504-X .
Schwenk, A. J. (1989), „Enumeration of Hamiltonian cycles in certain generalized Petersen graphs”, Journal of Combinatorial Theory, Series B, 47 (1), pp. 53–59, doi:10.1016/0095-8956(89)90064-6 
Zhang, Cun-Quan (1997), Integer Flows and Cycle Covers of Graphs , CRC Press, ISBN 978-0-8247-9790-4 .
Zhang, Cun-Quan (2012), Circuit Double Cover of Graphs, Cambridge University Press, ISBN 978-0-5212-8235-2 .

Legături externe

[8] Așa cum este formulat, aceasta presupune că grafurile Cayley nu trebuie să fie neapărat conexe. Unele surse impun ca grafurile Cayley să fie conexe, ceea ce face graful vid cu două noduri să fie cel mai mic graf non-Cayley nod-tranzitiv; în raport cu definiția dată de aceste surse, graful lui Petersen este cel mai mic graf nod-tranzitiv conex care nu este Cauchy.

[15] Aceasta rezultă din faptul că este un graf Moore, întrucât orice graf Moore este cel mai mare graf regulat posibil cu gradul său și diametrul său.^[11]

[18] Grafurile cubice cu 6 și 8 noduri care maximizează numărul de arbori de acoperire sunt scările Möbius.

[1] Brouwer, Andries E., The Petersen graph

[2] Petersen, Julius (1898), „Sur le théorème de Tait”, L'Intermédiaire des Mathématiciens, 5, pp. 225–227

[3] Kempe, A. B. (1886), „A memoir on the theory of mathematical form”, Philosophical Transactions of the Royal Society of London, 177, pp. 1–70, doi:10.1098/rstl.1886.0002

[4] Knuth, Donald E., The Art of Computer Programming; volume 4, pre-fascicle 0A. A draft of section 7: Introduction to combinatorial searching

[5] Babai, László (1995), „Automorphism groups, isomorphism, reconstruction”, În Graham, Ronald L.; Grötschel, Martin; Lovász, László, Handbook of Combinatorics, I, North-Holland, pp. 1447–1540, Corollary 1.8, arhivat din original la 11 iunie 2010 .

[foster-6] Royle, G. "Cubic Symmetric Graphs (The Foster Census)." Arhivat în 20 iulie 2008, la Wayback Machine.

[7] Cameron, Peter J. (2004), „Automorphisms of graphs”, În Beineke, Lowell W.; Wilson, Robin J., Topics in Algebraic Graph Theory, Encyclopedia of Mathematics and its Applications, 102, Cambridge University Press, Cambridge, pp. 135–153, doi:10.1017/CBO9780511529993, ISBN 0-521-80197-4, MR 2125091 ; vezi în special p. 153

[9] Holton, D. A.; Sheehan, J. (1993), The Petersen Graph, Cambridge University Press, p. 32, ISBN 0-521-43594-3

[10] Pegg, Ed Jr. (2002), „Book Review: The Colossal Book of Mathematics” (PDF), Notices of the American Mathematical Society, 49 (9), pp. 1084–1086, Bibcode:2002ITED...49.1084A, doi:10.1109/TED.2002.1003756

[11] Albertson, Michael O.; Boutin, Debra L. (2007), „Using determining sets to distinguish Kneser graphs”, Electronic Journal of Combinatorics, 14 (1), p. R20, doi:10.37236/938  , MR 2285824 .

[hs60-12] Hoffman, Alan J.; Singleton, Robert R. (1960), „Moore graphs with diameter 2 and 3” (PDF), IBM Journal of Research and Development, 5 (4), pp. 497–504, doi:10.1147/rd.45.0497, MR 0140437 .

[13] Alspach, Brian; Zhang, Cun-Quan (1993), „Cycle covers of cubic multigraphs”, Discrete Math., 111, pp. 11–17 .

[14] László Lovász, Alexander Schrijver (1998), „A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs” (PDF), Proceedings of the American Mathematical Society, 126 (5), pp. 1275–1285, doi:10.1090/S0002-9939-98-04244-0

[16] Jakobson, Dmitry; Rivin, Igor (1999), On some extremal problems in graph theory, arXiv:math.CO/9907050  , Bibcode:1999math......7050J

[17] Valdes, L. (1991), „Extremal properties of spanning trees in cubic graphs”, Congressus Numerantium, 85, pp. 143–160 .

[biggs-19] Biggs, Norman (1993), Algebraic Graph Theory (ed. 2nd), Cambridge: Cambridge University Press, ISBN 0-521-45897-8

[20] DeVos, Matt; Nešetřil, Jaroslav; Raspaud, André (2007), „On edge-maps whose inverse preserves flows or tensions”, Graph theory in Paris, Trends Math., Basel: Birkhäuser, pp. 109–138, doi:10.1007/978-3-7643-7400-6_10, ISBN 978-3-7643-7228-6, MR 2279171 .

[21] Coxeter, H. S. M. (1950), „Self-dual configurations and regular graphs”, Bulletin of the American Mathematical Society, 56 (5), pp. 413–455, doi:10.1090/S0002-9904-1950-09407-5  .

[22] Watkins, Mark E. (1969), „A Theorem on Tait Colorings with an Application to the Generalized Petersen Graphs”, Journal of Combinatorial Theory, 6 (2), pp. 152–164, doi:10.1016/S0021-9800(69)80116-X 

[Bailey1997-23] Bailey, Rosemary A. (1997), Surveys in Combinatorics, Cambridge University Press, p. 187, ISBN 978-0-521-59840-8

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[a]

[8]

[9]

[10]

[11]

[12]

[13]

[b]

[14]

[15]

[c]

[16]

[17]

[18]

[19]

[20]

Graful lui Petersen
Graful lui Petersen este cel mai adesea desenat ca un pentagon cu o pentagramă în interior, cu cince spițe.
Numit după	Julius Petersen
Noduri	10
Muchii	15
Rază	2
Diametru	2
Grosime	5
Automorfisme	120 (S₅)
Număr cromatic	3
Index cromatic	4
Index cromatic fracționar	3
Gen	1
Proprietăți	Cubic Tare regulat Distanță-tranzitiv Snark