Each node has three edges, proof that we can make 4 pairs of nodes which are not connected

Question

Question. Graph $G$ has 8 nodes, each node has 3 edges. Proof that it is able to split the nodes into 4 pairs which is not connected each other.

For example, we can divide it like the picture shown below.

My approach.

I can solve this problem by dividing the possible cases into four.

When I set the nodes $V_1, V_2, \cdots, V_8$, WLOG Let $V_1$ and $V_2, V_3, V_4$ connected each other.

We can divide the cases into four, which is:

1. $V_2, V_3, V_4$ is all connected each other (So, there are three pairs connected each other)
2. Only two pairs of $V_2, V_3, V_4$ is connected each other
3. Only one pair of $V_2, V_3, V_4$ is connected each other
4. No pairs of $V_2, V_3, V_4$ is connected each other

The problem is, I think I can solve this problem in this way, but I think there is a better way.

What should it be?

Answer 1

Hint

Your computation will work but it is indeed a bit tedious, and would quickly be not feasible with higher number of nodes. If you want to do something "neat":

Call $G=(V,E)$ your graph, on 8 nodes, 3-regular, hence on 12 edges. Note that your problem is equivalent to

Find a perfect matching in the complement of $G$

Indeed If you find a perfect matching in $G^c$ (the complement of $G$), then you will have a way to pair all nodes, with no edges (in $G$) between elements of a pair. Now your graph $G^c$ has 8 nodes, and is 4-regular. Do you have notions of perfect matching? and how to prove they exist?

To finish you could

Say that you have a 4-regular graph with $n=8$ nodes, hence the graph must be connected. Hence the graph includes an eulerian cycle. Select every other edges in this cycle and you end up with a 2 factors, made up of collection of even cycle. select every second edges in these cycles and you obtain the desired perfect matching.