A graph theory question: For given girth g, does there exist $n_0(g)$ such that any tree $T$ of even order $n \geq n_0(g)$ and maximum degree $\Delta(T) \leq 3$ can be completed to a cubic graph with girth $g$ and order $n$ (by adding $n/2 + 1$ edges)?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
Yes. First make $T$ cubic in any way. In each step, while the graph has a cycle whose length is less than $g$, pick a shortest cycle $C$ and one edge $uv$ of it. There are at most $6\cdot 2^g$ vertices whose distance is at most $g$ from $u$ or from $v$. Pick an edge $ab$ such that none of $a$ and $b$ are close to $u$ or to $v$. Delete $uv$ and $ab$ and add $ua$ and $vb$ to the graph. The length of any newly created cycle will be more than the length of $C$, so after finitely many steps this process terminates.
-
1$\begingroup$ When picking $ab\in E(C)$ you should state that $ab\notin E(T)$ which is of course possible. $\endgroup$– bofCommented Dec 9, 2022 at 21:55
-
1$\begingroup$ The procedure terminates with a graph whose girth is at least $g$ but how do you know the girth is exactly $g$? $\endgroup$– bofCommented Dec 9, 2022 at 21:57
-
$\begingroup$ Good points - I guess we can fix an edge that closes a cycle of length $g$ with $T$ (such an edge must exist), and never touch that later. $\endgroup$– domotorpCommented Dec 9, 2022 at 22:05
-
$\begingroup$ I was wondering if the additional edges can be chosen to be a cycle. Clearly it is impossible if $T$ has vertices of degree 2, but otherwise I think the same proof works if at each step we judiciously choose between adding $ua,vb$ or $ub,va$. $\endgroup$ Commented Dec 10, 2022 at 6:23
-