Reading the book on Graph theory written by Bondy and Murty (Springer), they present the following proof technique (Linear Indepence) to use when the combinatorial approach fail.
My questions are:
What makes the proof technique work on the specific case in the proof below ? They build a system of linear equations based on the decomposition of $K_n$ into complete bipartite graphs (CBG). Then they assume we have less than $n-1$ of these CBG's in the decomposition, which imply that there exist a non-trivial solution. And from this non-trivial solution we deduce a contradiction. However, I don't see where we use our decomposition in the proof other than constructing the system of equations in $n$ variables. Why couldn't I create this system in real-world and produce the contradiction ?
In general what makes the proof technique tick ?
It's a counting argument, so that's what makes it tick. So since $\mathcal{F}$ is a decomposition of $K_{n}$, we have the following: $$ \bigcup_{i=1}^{k} E(F_{i}) = E(K_{n}) $$
Subject to $E(F_{i}) \cap E(F_{j}) =\emptyset$, $\forall{i, j}$ with $i \neq j$.
The idea is that if we have $n-2$ or fewer linear equations associated with $\mathcal{F}$, then we have extra edges and another partition we haven't considered. Look at $K_{4}$. Let's consider the decomposition into $K_{2, 2}$, $K_{2}$, and $K_{2}$.
So since we are dealing with $K_{4}$, we are assuming at most $2$ subgraphs in the decomposition. I will chose the extremal cases: $K_{2,2}$ and $K_{2}$, which uses $5$ edges. However, we have a sixth edge (the second $K_{2}$), which we have not considered. Since $\mathcal{F}$ is a decomposition, that second $K_{2}$ is in $\mathcal{F}$. That's the contradiction underneath the linear equations.