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.



Decomposition of regular graphs
The answer is **no**.


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.


