Megoldás: 4.20
Ez többféleképpen is bizonyítható. Egyrészt megmutatható, hogy a Petersen-gráf bármely pontjából induló szélességi faváz éppen a
K.II.8.13. feladat megoldásában leírt favázat adja.
Egyszerűbb azonban a következő okoskodás. A
K.II.8.13. feladat megoldásában láttuk, hogy (izomorfiától eltekintve) egyetlen 10 pontú, 3-reguláris, 2-átmérőjű gráf van. Elég tehát belátni, hogy a Petersen-gráf is 2-átmérőjű (a másik két feltétel triviálisan teljesül). Tudjuk, hogy a Petersen-gráf csúcstranzitív, tehát elég belátni, hogy egy tetszőleges pontjából bármelyik másik pont elérhető legfeljebb 2 hosszú úttal. Ez könnyen ellenőrizhető.