Plane graphs without homeomorphically irreducible spanning trees

Ryo Nomura, Shoichi Tsuchiya

Research output: Contribution to journalArticlepeer-review


A homeomorphically irreducible spanning tree (HIST) of a graph G is a spanning tree without vertices of degree 2 in G. Malkevitch conjectured that every 4-connected plane graph has a HIST. In order to solve Malkevitch-conjecture, it is natural to show the existence of a HIST in 3-connected, internally 4-connected (or essentially 4-connected) plane graphs. In this paper, we construct 3-connected, internally 4-connected plane graphs without HISTs. Consequently, such a strategy does not work when we solve Malkevitch-conjecture.

Original languageEnglish
Pages (from-to)157-165
Number of pages9
JournalArs Combinatoria
Publication statusPublished - 2018 Oct
Externally publishedYes


  • Homeomorphically irreducible spanning tree (HIST)
  • Plane graph

ASJC Scopus subject areas

  • Mathematics(all)


Dive into the research topics of 'Plane graphs without homeomorphically irreducible spanning trees'. Together they form a unique fingerprint.

Cite this