# Partition a simple undirected graph with degree of every vertex at most 4 into two graphs with degree of every vertex at most 2

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$$?

• For future questions, you should include what you've attempted so far. Dec 5, 2020 at 16:27

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.)