Note on Perfect Forests

Research output: Contribution to journalArticlepeer-review

43 Downloads (Pure)

Abstract

A spanning subgraph F of a graph G is called perfect if F is a forest, the degree inline image of each vertex x in F is odd, and each tree of F is an induced subgraph of G. We provide a short linear-algebraic proof of the following theorem of A. D. Scott (Graphs Combin 17 (2001), 539–553): A connected graph G contains a perfect forest if and only if G has an even number of vertices.
Original languageEnglish
Pages (from-to)233-235
Number of pages3
JournalJournal of Graph Theory
Volume82
Issue number3
Early online date30 Jul 2015
DOIs
Publication statusPublished - Jul 2016

Cite this