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, 2020 at 16:27

1 Answer 1

1
$\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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .