3
$\begingroup$

I want to prove that ‘If the girth of a $2k$-regular graph $G$ is larger than the diameter of a $k$-edge tree $T$, then $G$ is covered by edge-disjoint copies of $T$.’
I tried several ways to solve this problem:

  1. Use the fact ‘If $\delta(G)\ge k$, $G$ contains a $k$-edge tree as a subgraph.’
  2. Consider the tree-packing and tree-covering problem.
  3. Create a proper algorithm.

I searched papers about this problem, and I found that Haggkvist proved it.
Here is the reference: page 130 of Decompositions of complete bipartite graphs.
But unfortunately, he said the manuscript containing his proof is not formally published.
So the only thing I know is this statement is true, and Haggkvist used it as a theorem.
But I cannot still find nice proof or strategy about it.
Would you help me?

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ I think there is a typo or a missing hypothesis. Perhaps you want $k \geq 2$? For example, the three-cycle (boundary of a triangle) has girth three, but is not edge-disjointly covered by paths of length two. $\endgroup$
    – Sam Nead
    Commented Sep 23, 2021 at 21:08
  • 2
    $\begingroup$ Hmm. The one-skeleton of the octahedron is $4$-regular, and has girth three. But it is not edge-disjointly covered by $4$-stars (trees with four leaves and one internal node). $\endgroup$
    – Sam Nead
    Commented Sep 23, 2021 at 21:11
  • 1
    $\begingroup$ @SamNead Oh, I am really sorry. As you mentioned, I missed a critical hypothesis: $T$ has $k$ edges. Now I revised it. Thank you. $\endgroup$
    – okw1124
    Commented Sep 23, 2021 at 21:14
  • $\begingroup$ Thank you. Nice problem! $\endgroup$
    – Sam Nead
    Commented Sep 24, 2021 at 6:14
  • $\begingroup$ Perhaps email Haggkvist and ask him for a copy of the preprint with the proof? $\endgroup$
    – Sam Nead
    Commented Sep 24, 2021 at 6:16

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .