Proof technique for packing constant-size paths with degree constraints in a tree with a perfect matching - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T03:43:39Z http://mathoverflow.net/feeds/question/80314 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/80314/proof-technique-for-packing-constant-size-paths-with-degree-constraints-in-a-tree Proof technique for packing constant-size paths with degree constraints in a tree with a perfect matching Bart Jansen 2011-11-07T17:15:43Z 2011-11-07T22:43:09Z <p>For my research I am interested in finding disjoint copies of certain "good structures" in graphs which are trees with a perfect matching. So let \$T\$ be a tree with a perfect matching \$M\$. I am interested in the following types of good structures:</p> <p>I) A path on four vertices \$(v_1, v_2, v_3, v_4)\$ such that vertices \$v_1\$ and \$v_4\$ are leaves of the tree (which implies that the edges \${v_1, v_2}\$ and \${v_3, v_4}\$ are contained in the matching), and</p> <p>II) A matching edge \${v_1, v_2}\$ such that both involved vertices have degree at most two in \$T\$.</p> <p>Say that a packing of good structures is simply a set of mutually vertex-disjoint subgraphs of \$T\$, where each subgraph has structure I or II. The result I am interested in is as follows: for each tree \$T\$ with a perfect matching on \$n\$ vertices, there is a packing of at least \$n/c\$ good structures, for some constant \$c\$ which is not too large. I can prove the theorem for \$c\$ about 15 or so by using a technique used by Griggs et al. ( Griggs, J.R., Kleitman, D., Shastri, A.: Spanning trees with many leaves in cubic graphs.) and later Kleitman and West, dubbed "amortized analysis by keeping track of dead leaves", which is used by them to prove lower-bounds on the number of leaves that you can find in spanning trees for certain graphs. The problem is: the proof requires a tedious case analysis. So I am looking for a cleaner way to prove this result, for a constant \$c\$ which is not bigger. I have tried to come up with an induction to capture what is going on, but to no avail. The problem is that when you find a good structure in a graph, remove it and apply induction on the remainder, then the removal of the good structure will change the degree of its neighboring vertices in the graph that is used for induction. Hence when we find a good structure in the remainder (by induction), they might not be good in the original graph because the degrees lowered by deleting the good structure we were looking at. Any suggestions or pointers to similar results in the literature are much appreciated.</p>