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.

  • 3
    $\begingroup$ 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. $\endgroup$ Jul 29, 2020 at 10:46
  • $\begingroup$ @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$? $\endgroup$
    – vidyarthi
    Jul 29, 2020 at 11:36
  • 2
    $\begingroup$ 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. $\endgroup$ Jul 29, 2020 at 12:18
  • $\begingroup$ @BrendanMcKay thanks! edited the post. The comment by Florian answers my main question anyways. $\endgroup$
    – vidyarthi
    Jul 29, 2020 at 12:20
  • 2
    $\begingroup$ 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. $\endgroup$ Jul 29, 2020 at 14:22

1 Answer 1


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.


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.