0
$\begingroup$

I have a graph having 6 vertices and its presentation is $E_{12}^4E_{13}^5E_{14}^6E_{24}^9E_{25}^2E_{35}^9E_{36}L_5^4L_6^{14}$. This means that there are $4$ edges connecting the vertices $1$ and $2$, there are $5$ edges connecting the vertices $1$ and $3$ and so on and there are $4$ loops at the vertex $5$ and there are $14$ loops at the vertex $6$. This is a $15$-regular graph if we have the convention that the loops contribute $1$ to the degree of a vertex.

It has a $5$-regular factor sub-graph having exactly 6 loops, that is $E_{12}^2E_{13}E_{14}^2E_{24}^3E_{35}^4L_5L_6^5$. This is just by trial and error method. Is there a theorem which ensures existence of such a factor ?

$\endgroup$
  • 1
    $\begingroup$ So you ask if $nm$-regular multigraph with $nk$ loops always has an $m$-regular sub-multigraph with $k$ loops? $\endgroup$ – Max Alekseyev May 5 at 20:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.