It's well known that any loopless graph $G = (V,E)$ with average degree bigger than $2p − 2$ and maximum degree at most $2p − 1$ contains a $p$-regular subgraph for any prime power $p$. But we don't know if it is true for all integers $p$. As an example or counterexample, I want to check the case with $p=6$, but it is not so easy.
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Isn't a loopless graph a forest, and therefore the average degree is always $\leq 1$? $\endgroup$– Bill BradleyCommented Apr 22 at 12:56
-
2$\begingroup$ @BillBradley I think “loopless” here means no self-links $(i,i)$ rather than no cycles. $\endgroup$– RobPrattCommented Apr 22 at 13:45
Add a comment
|