0
$\begingroup$

Suppose $G = (V, E)$ is a simple undirected graph (with no self-loop) such that the degree of every vertex is at most $4$. How to prove that it is possible to partition the edges $E$ into two sets $E_1$ and $E_2$ such that in each of the graphs $G_1 = (V, E_1)$ and $G_2 = (V, E_2)$, the degree of every vertex is at most $2$?

$\endgroup$
1
  • $\begingroup$ For future questions, you should include what you've attempted so far. $\endgroup$ – Hendrix Dec 5 '20 at 16:27
0
$\begingroup$

We have $G$ with $\Delta(G) \le 4$. Show that

There is some finite $4$-regular graph $R$ such that $G \subseteq R$.

The above statement generalizes nicely for any $\Delta(G)$. Then, we can apply Petersen's $2$-factor Theorem:

If a graph $G$ is $2k$-regular, then it has a $2$-factor. Consequently, $E(G)$ decomposes into $k$ many $2$-factors.

A $2$-factor is a $2$-regular spanning subgraph. There's a proof in the link, but you can also look at this MSE question to find an argument that generalizes nicely.

From these two, we can find a $4$-regular graph containing our graph, use the $2$-factor Theorem, and then delete vertices as required to obtain $G_1 = (V_1,E_1)$ and $G_2 = (V_2,E_2)$ as desired.

This is probably the way to think about it, but I wouldn't be surprised if there is another way using edge colorings. For example, the result follows immediately for Class $1$ graphs, but Class $2$ graphs may require a bit more thinking (See Edge Coloring.)

$\endgroup$

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.