Start with a grid $11\times11$, with $1$ in each square. Total is $22$.
Change $1$ to $-1$ in one square, new total is $18$.
Start with a grid $11\times11$, with random values. Change $1$ value, new total of rows increase or decrease by $2$, new total of columns increase or decrease by $2$, new total of rows+columns change by $-4, 0$ or $+4$.
Total is always equal to $2\pmod 4$. Total cannot be $0$, neither $4$ or $8$ or $12$ ...
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:
- You have an induction hypothesis that depends on a variable $n$. Lets call it $H_n$.
- You prove that $H_n$ is true for some $n=n_0$
- 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 :
- Start with a $4$-regular connected graphs $G$ on $n+1$ vertices. ANY such graph, without additional assumption.
- Modify it in some way to get a graph $G'$ on $n$ vertices, still $4$-regular connected.
- Apply the Induction hypothesis $H_n$ to deduce that there exists a desired coloring of $G'$.
- 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:
- A graph $G'$ on $n-1$ vertices,
- and a balanced red/blue coloring of $G'$,
- and two independent red and blue edges such that applying your process to these colored edges yields the graph $G$.
Best Answer
Give the squares of the grid coordinates $(x,y)$ where $0 \leq x, y \leq n-1$. Give the square $(x,y)$ colour $i$ where $0\leq i \leq n-1$, and $x+y \equiv i \pmod n$. This colouring satisfies the conditions required.