# Decomposition of regular graphs

Let $$G$$ be a regular simple graph with degree $$\Delta=n-k-1$$ and order $$m$$. Let $$C_k$$ be the regular graph which is formed by removing a $$k$$-factor from the complete graph $$K_{n}$$. I think we could always find a proper induced subgraph of $$C_k$$ with maximum degree at least $$\ge\frac{\Delta}{2}$$ as a subgraph of the graph $$G$$. Is this true?

If this be true, then I think to find the invariants of $$G$$, it suffices to find the invariants of $$C_k$$. Then, the invariants of $$G$$ would be related linearly with that of $$C_k$$. For example, the chromatic number/ index seems to be closely related to the number of disjoint copies of $$C_k$$ which occurs as an induced graph and $$m$$. In a way, I think this could be related to the tree-decomposition of the graph $$G$$. Any light on this? Thanks beforehand.

• There is more than one graph that can be obtained from $K_n$ by removing a $k$-factor (for $k = 2$, e.g. removing a Hamilton cycle vs removing two disjoint cycles covering all vertices gives different graphs). Neither of these graphs is a subgraph of the other. Jul 29, 2020 at 10:46
• @FlorianLehner thanks! so for regular graphs which contain certain copies of $C_k$ with a removal of a fixed $k$ factor, can we relate the graph invariant of $G$ with that of $C_k$? Jul 29, 2020 at 11:36
• I don't get it. $G$ and $C_k$ are both regular graphs of degree $\Delta$, so one can't be an induced subgraph of the other unless they are equal. I suspect you are not asking the question you intend to ask. Jul 29, 2020 at 12:18
• @BrendanMcKay thanks! edited the post. The comment by Florian answers my main question anyways. Jul 29, 2020 at 12:20
• It makes sense, but the answer is "no". The simplest example is if $\Delta=k$ then $C_k$ could be the complement of $G$ and so have no edges in common with $G$. If $\Delta$ is not far from $k$, it can still be true that $C_k$ and $G$ have too few common edges. Jul 29, 2020 at 14:22

Let $$G$$ be the Hoffman-Singleton graph (hence n=50, k=42). Let $$C_k$$ be the disjoint union of 5 $$K_8$$s and a $$K_{10}-C$$ ($$K_{10}$$ with a 10-cycle removed). Any proper induced subgraph of $$C_k$$ with maximum degree at least 4 will contain a $$C_3$$ or $$C_4$$, which $$G$$ does not contain.