The Graham-Pollak Theorem is a theorem in graph theory. This theorem assumes that there are n nations (let's say that we have 6 nations: A, B, C, D, E and F). The theorem then states that all fights between the nations can be covered in at least n-1 battles. But what is a fight and what is a battle? A fight is basically a nation vs another nation (example: A vs B, B vs C etc.). A battle is the same thing but multiple nations can participate (examples: A, B and C vs D, C and D vs E and F etc.). But what has this got to do with graph theory? Well, in more mathematical terms, the Graham-Pollak Theorem states that the edges of an n-vertex complete graph cannot be partitioned into fewer than n-1 complete bipartite graphs. The more intuitive definition of the theorem is just fine for this proof, though. So now, let's continue with the actual proof.
Observe that the first battle splits the nations into 3 groups: the nations that fought on the first side of the battle (G_1), the nations that fought on the second side of the battle (G_2), and the nations that didn't participate in the battle (G_3). Note: I will use m(G_i) to indicate the number of members in G_i. There are 2 types of battles: internal battles (battles between nations that are part of the same group) and external battles (battles between different groups). We observe that there are 3 external fights that must be accomplished: G_1 vs G_2 (the first battle), G_1 vs G_3 and G_2 vs G_3. The latter 2 fights can be combined into G_1 and G_2 vs G_3. So we get that the minimum number of external fights is 2 (if each group would be a nation, then we can easily see there would have to be at least 2 battles ). Now we just need to figure out the number of internal fights. Here is where mathematical induction starts.
We need to prove that the total number of battles is at least the number of nations - 1. First, we can easily observe that the base case, 1 nations, requires at least 0 battles. Then, our second step is proving that, if we know that k nations require k-1 battles, then k+1 nations require k battles. Here is where we start to get a system of inequalities. First, we know that for any group G_i, m(G_i)< k+1 (every battle has at least one nation on every side, so there can't be a group that contains all nations, even though G_3 can have 0 nations, but only if every nation participates in the first battle). Because of that, we know that all the internal battles of a group G_i require at least m(G_i) - 1 battles (the only exception being when m(G_3) = 0, but then we are left with only 2 groups and we get a similar proof). We also know that m(G_1)+m(G_2)+m(G_3)= k+1 (the groups don't overlap, and every nation is part of one group).
The total number of battles >= 2 external battles + the minimum number of internal battles. But the minimum number of internal battles is just the sum of the minimum number of battles required by each group. So we see that T (the total number of battles)>=2+m(G_1)-1+m(G_2)-1+m(G_3)-1=m(G_1)+m(G_2)+m(G_3)-1. But m(G_1)+m(G_2)+m(G_3)= k+1 (from above)! Substituting that, we get T>=k+1-1=k, so T>=k. But we have just proved is what we needed to prove.
A final note: I know this proof may have left our some things, and I acknowledge that the proof may be wrong. That is why I am asking the question, to see f the proof is correct.
If in fact we could divide all battles cleanly into "internal" and "external" ones, then the proof would be fine. But we can't.
Every fight (that is, every edge of the complete graph) can be classified as internal (an edge between two vertices of the same $G_i$) or external (an edge between two two vertices in $G_i, G_j$ with $i\ne j$). A battle, however, might include fights of both types.
Forgetting about the external fights for a moment, we see that it is to our advantage to have these mixed battles. Suppose that
Then we could accomplish both goals at once and have a battle with $A \cup C$ on one side and $B \cup D$ on the other. Induction does say that we need at least $|G_i|-1$ battles for all the fights internal to $G_i$ for $i=1,2,3$. However, this does not need to be $(|G_1|-1) + (|G_2|-1) + (|G_3|-1)$ battles total, because we can combine some of the battles together.
The reason that this does not disprove Graham–Pollak is that we pay for this efficiency in a different way. If we combine some of the internal battles into mixed battles, then we can no longer have a big external battle of $G_1 \cup G_2$ vs. $G_3$: some of those fights have already happened!
According to the Graham–Pollak theorem, it must be the case that in covering all the remaining fights between $G_1 \cup G_2$ and $G_3$, we use up all the battles we saved by having mixed battles. But this is by no means obvious.
Your proof does not address this issue at all: you assume that if the first battle is $G_1$ vs. $G_2$, then either $G_3 = \varnothing$ or else a battle $G_1 \cup G_2$ vs. $G_3$ will happen. This assumption is false. For example, the solution below (taken from Wikipedia) does not have this property, no matter which battle you pick to be the first battle defining $G_1, G_2, G_3$.