Every tree contains a large induced subgraph with all degrees odd

✍ Scribed by A.J. Radclife; A.D. Scott

• Publisher: Elsevier Science
• Year: 1995
• Tongue: English
• Weight: 222 KB
• Volume: 140
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(93)e0186-8

✦ Synopsis

Caro et al. proved that every tree of order n contains an induced subgraph of order at least rn/2] with all degrees odd, and conjectured a better bound. In this note we prove that every tree of order n contains an induced subgraph of order at least 2L(n + 1)/3 .] with all degrees odd; this bound is best possible for every value of n.

Gallai (see I-4, Section 5, Problem 17]) proved that we can partition the vertices of any graph into two sets, each of which induces a subgraph with all degrees even; we can also partition the vertices into two sets so that one set induces a subgraph with all degrees even and the other induces a subgraph with all degrees odd. As an immediate consequence of this, we see that every graph of order n contains an induced subgraph of order at least Fn/2-] with all degrees even.

It is natural to ask whether we can partition every graph into induced subgraphs with odd degrees, but this turns out not to be possible (consider, for instance, Ca). However, the results for induced subgraphs with even degrees suggest the following conjecture, the origin of which is unclear (see 1-2]).

Conjecture.

There exists e>O such that every connected graph G contains some Wc V(G) with I W[ ~>~IGI such that the graph induced by W has all degrees odd.

Caro J2] proved that we can demand I WI ~>c Ix/~, and Scott 1'5] proved that we can get I WI >~clGI/log(I GI). If the conjecture is true, then an example of Caro shows