Two short proofs of the Perfect Forest Theorem

DOI10.20429/TAG.2017.040104zbMATH Open1416.05222arXiv1612.05004OpenAlexW2577009393WikidataQ113728312 ScholiaQ113728312MaRDI QIDQ5225532FDOQ5225532

Authors: Yair Caro, Josef Lauri, Christina Zarb 

Publication date: 22 July 2019

Published in: Theory and Applications of Graphs (Search for Journal in Brave)

Abstract: A perfect forest is a spanning forest of a connected graph $G$, all of whose components are induced subgraphs of $G$ and such that all vertices have odd degree in the forest. A perfect forest generalised a perfect matching since, in a matching, all components are trees on one edge. Scott first proved the Perfect Forest Theorem, namely, that every connected graph of even order has a perfect forest. Gutin then gave another proof using linear algebra. We give here two very short proofs of the Perfect Forest Theorem which use only elementary notions from graph theory. Both our proofs yield polynomial-time algorithms for finding a perfect forest in a connected graph of even order.

Full work available at URL: https://arxiv.org/abs/1612.05004

Recommendations

• Note on Perfect Forests
• Perfect forests in graphs and their extensions
• Note on Perfect Forests in Digraphs
• A simple a. s. correct algorithm for deciding if a graph has a perfect matching
• Perfect pairs of trees associated with a prescribed tree: An algorithmic approach

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (4)

• Title not available (Why is that?)
• Generalized matchings in forests
• Perfect forests in graphs and their extensions
• Perfect distance forests

This page was built for publication: Two short proofs of the Perfect Forest Theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5225532)