Every 4-regular connected simple graph edges can be colored with 2 colors so each vertex has 2 edges of each color, why the prove isn’t working

coloringgraph theoryproof-explanation

I've tried the following proof, but my professor said it's wrong and didn't explain why but told me "you can't do induction this way", can someone elaborate on his behalf?

  1. Let $G=(V,E)$ .We'll prove with induction on $|V|$
  2. Basis: the least graph that is 4-regular and connected is $K_5$, we'll show that it can be colored in 2 colors as needed:
    graph coloring as needed

3. Inductive assumption: suppose $|V|=n$, and it satisfies the needed.
4. Step: we'll prove the desired for $|V|=n+1$ by building such graph.
5. We'll pick any 2 edges (that are not sharing a vertex) blue one and red one, and remove those edges.
6. Add a new vertex and connect it to the vertices that we're detached corresponding to the color of the edge they were detached by.
7. This new vertex would have a degree of 4, and have 2 blue and 2 red edges, the other vertices returned to have a degree of 4, and 2 edges of each color.
8. The new graph that was built this way is still 4-regular and connected, and now satisfies the needed.

I've seen an option to prove it using the existence of Eulerian circuit, but I'm still curious to understand why mine doesn't work.

Best Answer

Your mistake is a very usual wrong use of induction. And I think it is really important for your math studies that you understand the mistake.

In general, an induction proof should work as follows:

  1. You have an induction hypothesis that depends on a variable $n$. Lets call it $H_n$.
  2. You prove that $H_n$ is true for some $n=n_0$
  3. You prove that for all $n$, if $H_n$ is true, then $H_{n+1}$ is true.

This implies that for all $n\geq n_0$, $H_n$ is true.

Now looking at your "proof". We have,

$H_n$: "Every $4$-regular connected simple graph on $n$ vertices admits a red/blue edge-coloring such that each vertex is incident with two red and two blue edges."

You need to prove that $H_n$ is true for some $n_0$. You selected $n_0=5$. You proved that the statement is true for $K_5$. But the assumptions says "EVERY $4$-regular connected simple graph on $n$ vertices". Therefore to prove that $H_{5}$ is true, you need to argue that $K_5$ is the only $4$-regular graph on $5$ vertices.

But the main issue is in the last step. You are starting with a graph that satisfies the assumption, and building another larger one that still does. As mentioned in the comment how do you know that EVERY $4$-connected simple graph can be built in that way ? If you want to prove the statement by induction you need to :

  1. Start with a $4$-regular connected graphs $G$ on $n+1$ vertices. ANY such graph, without additional assumption.
  2. Modify it in some way to get a graph $G'$ on $n$ vertices, still $4$-regular connected.
  3. Apply the Induction hypothesis $H_n$ to deduce that there exists a desired coloring of $G'$.
  4. Reverse the process to show that $G$ also admits a desired coloring.

Do you understand the difference ?

One way to solve your proof would then be to prove that ANY $4$-connected simple graph can be obtained from $K_5$ with your process, but it might be tricky as your process already depends on the coloring. To be precise, you'd need to prove that, for any $4$-regular connected graph on $n>5$ vertices, there exist:

  1. A graph $G'$ on $n-1$ vertices,
  2. and a balanced red/blue coloring of $G'$,
  3. and two independent red and blue edges such that applying your process to these colored edges yields the graph $G$.
Related Question