Disconnected computers

If we represent each computer as a vertex of a graph, and direct connection between computers to be an edge between the two vertices, we now have a graph representing the connections. The condition of the problem means the graph is triangle-free: it doesn't contain three vertices, each adjacent to each other. By Mantel's theorem, a simple triangle-free graph of $n$ vertices has at most $\left\lfloor \frac{n^2}{4} \right\rfloor$ edges, so since $n = 30$ , we have $\left\lfloor \frac{30^2}{4} \right\rfloor = \boxed{225}$ edges, achievable by the complete bipartite graph $K_{15,15}$ : 15 vertices in one group and 15 in the other, and there is an edge between two vertices of different groups (and none in the same group).

---

That was not very satisfactory, huh? Just a single application of the theorem. So let's prove the theorem. (This follows the same proof in Wikipedia.) Mantel's theorem is a special case of Turan's theorem. (Turan's theorem gives the number of edges for a graph that doesn't have $K_r$ : $r$ vertices, each adjacent to each other; Mantel's theorem is $r = 3$ .) Both are example theorems in the field of extremal graph theory , a subfield of graph theory where we look at extremes: graphs with most/least vertices, edges, cycles, whatever else, subject to certain conditions.

The proofs of such theorems generally follow the same structure: take the extreme example, and prove statements about it that must hold.

In the following, all graphs are simple. $\deg v$ is the degree of $v$ ; that is, the number of edges incident to $v$ .

Let $G$ be a graph of $n$ vertices that is triangle-free and has the most number of edges. (We want to find the number of edges in $G$ to prove Mantel's theorem. Also note that we can do so because there is an upper bound on the number of edges and the number of edges is an integer, so there must be a maximum.) We have a claim:

Claim 1 : $G$ doesn't contain three vertices $u,v,w$ where $uv$ is an edge but $uw, vw$ aren't. That is, for any three vertices, there must be either zero or two edges among them.

Suppose otherwise. We want to construct a new graph $G'$ of $n$ vertices that is still triangle-free but has more edges than $G$ ; this would contradict the fact that we chose $G$ to have the most number of edges. We can divide into two cases:

Case 1 : $\deg w < \deg u$ or $\deg w < \deg v$

Without loss of generality, suppose $\deg w < \deg u$ (otherwise swap the names of $u$ and $v$ ). Delete $w$ (with all edges incident to it) and replace it with a copy of $u$ named $u'$ ; every neighbor of $u$ is also a neighbor of $u'$ and vice versa. $u$ and $u'$ themselves aren't adjacent. Since the original graph doesn't contain any triangle, the graph after deleting $w$ also doesn't contain any triangle. When we introduce $u'$ , there is also no triangle. For, if $u', x, y$ make a triangle, then neither of $x,y$ can be $u$ because $uu'$ is not an edge. So $u'x, u'y, xy$ are edges, thus by definition of $u'$ , we know that $ux, uy, xy$ are also edges. But this means $u, x, y$ make a triangle, which implies the original graph is not triangle-free, contradiction. So our new graph is triangle-free. Moreover, since $\deg w < \deg u$ , we erased $\deg w$ edges but added $\deg u$ edges, for a total of $\deg u - \deg w > 0$ edges. This means $G'$ has more edges than $G$ , contradiction.

Case 2 : $\deg w \ge \deg u, \deg v$

Similar to before, we delete and make copies. This time, we delete both $u$ and $v$ , and make two new copies of $w$ named $w', w''$ . Similar to before, there is no triangle not involving $w'$ nor $w''$ . A triangle involving $w'$ , say $w', x, y$ , implies that $w'x, w'y, xy$ are edges, and hence $wx, wy, xy$ are edges, and hence $w, x, y$ is also a triangle, contradiction. Similar with a triangle involving $w''$ . So our new graph is triangle-free. But how many edges were deleted and introduced? We deleted $\deg u$ edges from $u$ , plus $deg v$ edges from $v$ ; however, one of the edges is counted twice, because $uv$ is an edge and thus contributes one for both $u$ and $v$ . Thus we only lose $\deg u + \deg v - 1$ edges, and we gain $2 \cdot \deg w$ edges from the two copies. That's a net gain of $2 \cdot \deg w - (\deg u + \deg v - 1) = (\deg w - \deg u) + (\deg w - \deg v) + 1 \ge 0 + 0 + 1 > 0$ edges, so $G'$ has more edges than $G$ as well, contradiction.

Thus we have proven Claim 1.

Now, for each vertex in $G$ , give it a color such that two vertices that are not adjacent have the same color and two vertices that are adjacent have different colors. We can do this, because of Claim 1:

• If $u,v$ are not adjacent, then they have the same color. If $v,w$ are not adjacent, then they have the same color. By Claim 1, if $u,v$ are not adjacent and so as $v,w$ , then $u,w$ are also not adjacent; indeed, they do have the same color, because all of $u,v,w$ are of the same color.
• Similar to above; suppose $u,v$ are not adjacent. If $v,w$ are adjacent, then they have different colors. Thus $u,w$ also have different colors (because $u,v$ have the same color but $v,w$ have different colors). Indeed, by Claim 1, $u,w$ must be adjacent.

Technically speaking, we can partition the vertices of $G$ into equivalence classes, where two vertices are equivalent if and only if they are not adjacent.

Now, if there are three colors, suppose $u, v, w$ are colored by the first, second, and third colors respectively. This means $u,v,w$ must be all adjacent to each other (because any two of them have different colors). But this means they form a triangle, contradiction. So there are at most two colors. We can divide the vertices into two groups $A$ and $B$ , having $a$ and $b$ vertices respectively, where two vertices in different groups are adjacent and two vertices in the same group are not adjacent.

Finally, we show that $|a-b| \le 1$ ; that is, the division must be as small as possible. This one is straightforward: $a+b = n$ , the number of vertices, is fixed, and we want to maximize $ab$ , the number of edges. Without loss of generality, $a \le b$ (otherwise swap the names $A$ and $B$ ). If $a \le b-2$ , consider moving one vertex from $B$ to $A$ , so we have $a' = a+1, b' = b-1$ . We have $a'b' = (a+1)(b-1) = ab + b - a - 1 \ge ab + 2 - 1 > ab$ , so we can make a graph with more edges, contradiction. So $a \ge b-1$ , and since $a \le b$ , this proves the claim that $|a-b| \le 1$ . There is only one such possibility: $a = \left\lfloor \frac{n}{2} \right\rfloor, b = \left\lceil \frac{n}{2} \right\rceil$ , and we can check the two cases ( $n$ even and $n$ odd) that $ab = \left\lfloor \frac{n^2}{4} \right\rfloor$ , as required.