I'm doing the exercise 5.10 at page 30 of Wilson's Introduction to Graph Theory. It says:
Let $G$ be a simple graph on $2k$ vertices containing no triangles. Show, by induction on $k$, that $G$ has at most $k^2$ edges.
The adjacency matrix of $G$ must be a square matrix of dimension $2k$, and if one cancels the $i$-th and $j$-th rows and columns, the result is the adjacency matrix of the graph $G$ with the two vertex $i$ and $j$ deleted. I recall that the trace of the square of an adjacency matrix is twice the total number of edges in the graph, and that the trace of the cube of an adjacency matrix is the total number of triangles multiplied by $6$. This means that, named $A$ the adjacency matrix of $G$, the $2k$ elements on the diagonal of $A^2$ are such that the sum of $2k-2$ of them is always less than $(k-1)^2$, by the inductivity hypotesis. So in general, if we have $2k$ numbers with this property, the sum of all the numbers can be bounded in this way: $$(k-1)^2\frac {2k\choose {2k-2}}{{2k-1}\choose {2k-3}}.$$ This seems right to me, since the number of distinct $2k-2$-uples in a set with $2k$ elements is the numerator of the fraction, but every element belongs to a number of $2k-2$-uples equal to the denominator. With these calculations I obtain that the total sum of the $2k$ numbers is bounded by $$\frac{k^3-k^2-k+1}{k}.$$ However this value is strictly less than $k^2$, and this can't be true since the upper bound of Turàn's theorem can be easily achieved, for example with the wheel graph $W_6$. What am I missing? I would like to know in particular where is the mistake in this proof, I'm not just interested in a proof of the theorem. Thanks in advance for the help.
Working with the adjacency matrix is rarely as helpful as it first seems, and in this case it obscures your argument. In particular, instead of saying that "the trace of $A^2$ is twice the number of edges", we may say "the sum of degrees in a graph is twice the number of edges" and get an equivalent argument.
So in more conventional language, you're saying that
This seems like it ought to work: deleting any two vertices leaves a $2k-2$-vertex graph with no triangles. And you're right that if it did work, we can bound the sum of all degrees: if we add up all $\binom{2k}{2k-2}$ such sums, then each degree is added $\binom{2k-1}{2k-3}$ times, leading to $\frac{\binom{2k}{2k-2}}{\binom{2k-1}{2k-3}} (k-1)^2 = k(k-1)$.
But if we delete two vertices $v$ and $w$, the degrees in the remaining graph $G - v - w$ are not the same as the degrees in the original graph $G$. Every vertex adjacent to $v$ or to $w$ will have its degree go down by $1$ (and if a vertex is adjacent to both, its degree will go down by $2$). That's why we can't conclude that $G$ has at most $k(k-1)$ edges.
To put it differently, here is the sum that lets us use the inductive hypothesis: $$ \sum_{v \in V} \sum_{w \in V-v} \left(\sum_{u \in V-v-w} \deg_{G-v-w}(u)\right) = \sum_{v \in V} \sum_{w \in V-v} 2|E(G-v-w)| \le \binom {2k}2 \cdot 2(k-1)^2 $$ And here is the sum where $\deg_G(u)$ is counted $\binom{2k-1}{2}$ times: $$ \sum_{v \in V} \sum_{w \in V-v} \sum_{u \in V-v-w} \deg_G(u) = \binom{2k-1}{2}\sum_{u \in V} \deg_G(u) = \binom{2k-1}{2} (2|E(G)|). $$ These are not the same: in the first sum, to get the number of edges in $G-v-w$, we have to take the degree of $u$ in $G-v-w$. In the second sum, to get the number of edges in $G$ at the end, we have to take the degree of $u$ in $G$. Those are different.
The same problem will appear in the adjacency matrix calculation (because the adjacency matrix calculation is really just another way to phrase the same argument). If you delete rows and columns $i$ and $j$ from $A$ to get a matrix $B$, the $2k-2$ diagonal entries of $B^2$ will not agree with $2k-2$ of the $2k$ diagonal entries of $A^2$. A typical diagonal entry of $A^2$ is $$(A^2)_{kk} = \sum_{\ell=1}^{2k} A_{k\ell} A_{\ell k}$$ and when we pass to $B^2$, the two terms $A_{ki} A_{ik}$ and $A_{kj} A_{jk}$ disappear.
But it's okay, we can fix this! You'll just have to do a bit more work along the way. Pick the two vertices $v,w$ to delete (or, if you insist, the two rows and columns to delete). By the inductive hypothesis, $G-v-w$ has at most $(k-1)^2$ edges. How many edges of $G$ are not edges of $G-v-w$? There's $\deg(v) + \deg(w)$ if $v$ and $w$ are not adjacent, or $\deg(v) + \deg(w) - 1$ if they are (because the edge $vw$ is counted twice by $\deg(v)+\deg(w)$).
Can you pick $v$ and $w$ in such a way that there are at most $k^2 - (k-1)^2$ of these missing edges? If so, you'll get a proof of Mantel's theorem.