1
$\begingroup$

I think this question is related to 'Any $2k$-regular graph can be $k$-factored', but I have no idea how to use this fact to solve the problem.
I also tried to use 'If $T$ is a tree with $k$ edges and $\delta(G)\geq k$, $T \subset G$'.
But I cannot repeat applying this to given $G$ since $\deg(v) \leq k$ for $v \in V(T)$ so that $\delta(G-T) \geq k$, and if I do it once more, $\delta(G-T-T') \geq 0$ for $T'$ the copy of $T$, then I cannot assure $G-T-T'$ contains $T$ as its subgraph.
The only thing I know is there should be one more condition: the girth of $G$ should be larger than $\mathrm{diam}(T)$.
Otherwise, $T$ cannot cover the smallest cycle in $G$.
Would you help me?

$\endgroup$
7
  • $\begingroup$ Frankly speaking, the formulation of the problem is not very clear. Let $T$ be an arbitrary tree with $k$ edges, and let $G$ be a regular graph of degree $2k$. Then $G=\cup T_i$ where $T_i\cong T$ for all $i$. Did I understand you correctly? $\endgroup$
    – kabenyuk
    Sep 21, 2021 at 12:01
  • $\begingroup$ @kabenyuk Exactly right! Sorry for informal words, I am just in my first step with Graph theory. $\endgroup$
    – okw1124
    Sep 21, 2021 at 12:56
  • 2
    $\begingroup$ Where did you find this problem ? Are you sure you wrote it correctly here ? Are you trying to prove that any $2k$-regular graph can be decomposed into edge-disjoint copies of any tree on $k$ edges ? Just taking $G$ the complete graphs on $2k+1$ graph is extremely completed, called Ringel's conjecture and proved only very recently by Montgomery, Pokrovskiy and Sudakov. See quantamagazine.org/… for a nice presentation. $\endgroup$ Sep 22, 2021 at 0:32
  • 2
    $\begingroup$ Or are you asking : for any $2k$-regular graph, there exists one tree $T$ on $k$ edges such that $G$ can be decomposed into edge-disjoint copies of $T$ $\endgroup$ Sep 22, 2021 at 0:33
  • 2
    $\begingroup$ Sorry I had missed the information on girth and diameter! I'll think about it $\endgroup$ Sep 22, 2021 at 23:33

2 Answers 2

2
+50
$\begingroup$

Edit: It seems that my proof works only if the girth is strictly larger than the diameter of $T$.


Color each one of the $k$ edges of the tree with a different color, and give it an arbitrary orientation.
Every $2k$-regular graph is $2$ factorable, so we can give an edge coloration with $k$ colors. On each cycle of the factorization, orient all the edges consistently. That way, each vertex has one incoming and one outgoing edge, of each color.

Take an edge of the graph, and find its corresponding edge in the tree. From it, add incrementally edges of the graph according to the tree. At each edge, as every type of edge is present in every direction, it will always be possible to build the tree. The subgraph so constructed has no cycle due to the girth condition. Thus the subgraph is a tree. By construction, we see that, for each edge, the corresponding tree is uniquely defined. So we can repeat the process and cover the entire graph.

$\endgroup$
6
  • 1
    $\begingroup$ I think you have a typo. The second sentence should (?) be "Every $2k$-regular graph is $2$-factorable, so...". $\endgroup$
    – Sam Nead
    Sep 25, 2021 at 14:57
  • $\begingroup$ Does each tree $T_i$ need to embed? (That is, no distinct pair of vertices $u$ and $v$ of $T_i$ are sent to a single vertex of $G$. Your construction ensures that distinct edges are sent to distinct edges.) If that is not a requirement (and I don't see it stated) then I think your proof works regardless of the girth of $G$. $\endgroup$
    – Sam Nead
    Sep 25, 2021 at 14:58
  • 1
    $\begingroup$ From the definition of decomposition, we need subgraphs, so each vertex of the tree needs to be associated with a single vertex of the graph. But you made me realize that my proof requires a girth at least $diam(T)+1$, whereas the paper of Haggkvist speaks of a girth of at least $diam(T)$. If the subgraphs are required to be induced, girth needs to be at least diameter $diam(T)+2$ in my proof, but it doesn't seem like Haggkvist requires this. $\endgroup$
    – caduk
    Sep 25, 2021 at 15:27
  • $\begingroup$ Sorry for late response, but can you explain more about 'add incrementally edges of the graph according to the tree' and 'every direction' part? Also, I cannot follow 'the corresponding tree is unique' part. I would appreciate it if you give more advice. $\endgroup$
    – okw1124
    Dec 11, 2021 at 7:20
  • $\begingroup$ Now I understood that part...but can we assure that we can repeat this process until we cover the entire graph? $\endgroup$
    – okw1124
    Dec 11, 2021 at 7:37
0
$\begingroup$

Since I completed a more concrete solution, I post another answer.
Let $G$ be a graph with $\vert V(G) \vert = n$ and $T$ be a tree with $V(T)=\{v_1,\cdots,v_{m+1}\}$.

Claim: $G$ is decomposed to $n$ copies of $T$, say $T_1,\cdots,T_n$, and for arbitrary $i$, the corresponding vertices to $v_i$ in $G$ are different among all copies of $T$.

Lemma: Every $2k$-regular graph is $2$-factorable.

We will use mathematical induction on $m$.
For basis, when $m=1$, the statement is true since we can find a decomposition of a cycle (or a disjoint union of cycles) with $n$ edges satisfying the statement.
Suppose the statement holds for all $m \leq k-1$.
Now consider $m=k$ case.
By the lemma, $2k$-regular graph $G$ has a $2$-factor.
Delete one $2$-factor, say $C$, from $G$.
Now we get $2(k-1)$-regular graph.
By IH, this $2(k-1)$-regular graph is decomposed to $n$ copies of a tree $T'$ with $k-1$ edges, say $T_1',\cdots,T_n'$.
WLOG assume $T'=T-v_{k+1}$ where $v_{k+1}$ is a leaf of $T$ adjacent to $v_k$.
It suffices to show by adding $C$ again, we can construct $T$ from each of the copies of $T'$ where the corresponding vertices to $v_{k+1}$ in $G$ are not duplicated.
Here, observe that since all $n$ copies of $v_k$ in $T_1',\cdots,T_n'$ are different, so they cover all $n$ vertices of $G$.
And also, $C$ covers all vertices of $G$.
Now give an orientation to $C$ 'consistently' so that each vertex has one in-coming edge and one out-going edge.
Then for each copy of $v_k$, there is exactly one out-going edge from $v_k$.
For each $T_j'$, select this out-going edge for the copy of $\{v_k,v_{k+1}\}$.
Now the copies of $v_{k+1}$ are not duplicated in $G$ by the construction of the orientation on $C$.
Also, $T_j' \cup \{v_k,v_{k+1}\}$ forms $T_j$.
Moreover, since there are $n$ copies of $\{v_k,v_{k+1}\}$, we used all $n$ edges of $C$ - we covered entire $G$ by the copies of $T$.
Note that $T_j$ in $G$ does not contain a cycle by the girth condition. $\square$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.