ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume


Z. Skupień

Zdzisław Skupień

Faculty of Applied MathematicsAGH University of Science and Technologyal. Mickiewicza 3030-059 KrakówPOLAND



The Petersen and Heawood graphs make up graphical twins via induced matchings



Discussiones Mathematicae Graph Theory 43(3) (2023) 677-683

Received: 2020-07-20 , Revised: 2021-01-26 , Accepted: 2021-01-26 , Available online: 2021-02-21 ,


Inspired by the Isaacs remark (published in 1975), we show that the Petersen and Heawood graphs ($Pg$ and $Hg$) make up a bijectively linked pair of graphs. Another related new result is that $Pg$ is uniquely decomposable into five induced 3-matchings. It shows a kind of the structural rigidity of $Pg$. Information on maximal matchings with sizes 3, 4 and 5 in $Pg$ is recalled. Constructive proofs confirm that the strong chromatic index $sq(Pg)=5$ and $sq(Hg)=7$. The three numerical edge coloring partitions for $Pg$ are also determined.


Heawood graph, induced matchings, Petersen graph, strong chromatic index


  1. G.M. Adel'son-Vel'skiǐ and V.K. Titov, On edge $4$-chromatic cubic graphs, in: Proc. Conf. held at Moscow Univ. in Jan. 27–29, 1971, Voprosy Kibernetiki (1973) 5–14, in Russian.
  2. J.-C. Bermond, J.M.S. Simões-Pereira and C.M. Zamfirescu, On non-Hamiltonian homogeneously traceable digraphs, Math. Japon. 24 (1979/80) 423–426.
  3. G. Chartrand, R.J. Gould and S.P. Kapoor, On homogeneously traceable nonhamiltonian graphs, in: Proc. 2nd Internat. Conf. on Combinat. Math., Ann. New York Acad. Sci. 319 (1979) 130–135.
  4. R.J. Faudree, R.H. Schelp, A. Gyárfás and Zs. Tuza, The strong chromatic index of graphs, Ars Combin. 29B (1990) 205–211.
  5. R.J. Gould, Degree sets for homogeneously traceably non-Hamiltonian graphs, Colloq. Math. 45 (1981) 155–158.
  6. P.J. Heawood, Map-colour theorem, Quart. J. Math. Oxford Ser. 24 (1890) 332–338.
  7. D.A. Holton and J. Sheehan, The Petersen Graph (Cambridge Univ. Press, Cambridge, 1993).
  8. R. Isaacs, Infinite families of non-trivial trivalent graphs which are not Tait colorable, Amer. Math. Monthly 82 (1975) 221–239.
  9. J. Petersen, Sur le théorème de Tait, L'intermédiaire des Mathématiciens 5 (1898) 225–227.
  10. Z. Skupień, Homogeneously traceable and Hamiltonian connected graphs (1976), preprint.
  11. Z. Skupień, Degrees in homogeneously traceable graphs, Ann. Discrete Math. 8 (1980) 185–188.
  12. Z. Skupień, Maximum degree among vertices of a non-Hamiltonian homogeneously traceable graph, in: Combinatorics and Graph Theory, S.B. Rao (Ed(s)), Lecture Notes in Math. 885 (1981) 496–500.
  13. Z. Skupień, On homogeneously traceable nonhamiltonian digraphs and oriented graphs, in: The Theory and Applications of Graphs, G. Chartrand, Y. Alavi, D.L. Goldsmith, L. Lesniak-Foster and D.R. Lick (Ed(s)), (Wiley, New York 1981) 517–527.
  14. Z. Skupień, Homogeneously traceable and Hamiltonian connected graphs, Demonstr. Math. 17 (1984) 1051–1067.
  15. M.M. Sysło and Z. Skupień, Applied Graph Theory III Euler and Hamilton graphs. Saleman problem, Math. Appl. (Warsaw) X (1977) 5–54, in Polish.
  16. T. Zamfirescu, Three small cubic graphs with interesting Hamiltonian properties, J. Graph Theory 4 (1980) 287–292.