Kvant Math Problem 416

Interpret the drawn segments as the edges of a graph whose vertices are the given points.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m34s
Source on kvant.digital

Problem

On the plane, $n$ points $A_1$, $\ldots$, $A_n$ are given, no three of which lie on the same line. What is the greatest number of line segments with endpoints at these points that can be drawn so that no triangle with vertices at these points is formed?

A. Grigoryan, M. Primak, S. Fishbein

Exploration

Interpret the drawn segments as the edges of a graph whose vertices are the given points. The condition that no triangle with vertices among the given points is formed means that the graph contains no cycle of length $3$.

The geometric condition that no three points are collinear seems relevant at first, because edges are drawn as straight segments. However, a triangle with vertices $A_i,A_j,A_k$ is formed exactly when all three sides $A_iA_j$, $A_jA_k$, $A_kA_i$ are present. Since no three points are collinear, any three vertices connected pairwise indeed determine a genuine triangle. Thus the problem becomes purely graph-theoretic: what is the largest number of edges in a triangle-free graph on $n$ vertices?

Try small values.

For $n=2$, the maximum is $1$.

For $n=3$, at most $2$ edges can be drawn; three edges would form a triangle.

For $n=4$, a square gives $4$ edges and no triangle. A graph with $5$ edges is the complete graph $K_4$ minus one edge; among the three vertices not incident with the missing edge there is a triangle. Hence $4$ is maximal.

These values suggest

$$1,\ 2,\ 4,\ldots$$

which agrees with

$$\left\lfloor \frac{n^2}{4}\right\rfloor.$$

A natural extremal example is to divide the vertices into two groups of sizes as equal as possible and join every vertex of one group to every vertex of the other. This complete bipartite graph has no triangles and contains

$$ab$$

edges when the parts have sizes $a,b$, $a+b=n$. The product $ab$ is maximal when the parts are as equal as possible, yielding

$$\left\lfloor \frac{n^2}{4}\right\rfloor.$$

The difficult part is proving that no triangle-free graph on $n$ vertices can have more edges. The classical argument uses induction. Choose a vertex of maximum degree $d$. Remove it and all its neighbors. Since the graph is triangle-free, no two neighbors are adjacent. The remaining graph has $n-d-1$ vertices. If $e$ denotes the number of edges, then

$$e\le d(n-d)+\left\lfloor\frac{(n-d-1)^2}{4}\right\rfloor.$$

One must check that the right-hand side never exceeds $\lfloor n^2/4\rfloor$. This is the step most likely to conceal an error.

Problem Understanding

We are given $n$ points in the plane, no three on one line. Segments may be drawn between pairs of points. We seek the greatest possible number of drawn segments under the condition that no triangle whose vertices are among the given points is formed.

This is a Type C problem. We must determine the maximal number of segments, construct a configuration attaining it, and prove that no larger number is possible.

The geometric condition merely guarantees that whenever three vertices are joined pairwise, they form an actual triangle. Hence the problem is equivalent to finding the maximum number of edges in a triangle-free graph on $n$ vertices.

The expected answer is

$$\left\lfloor \frac{n^2}{4}\right\rfloor.$$

A complete bipartite graph with parts as equal as possible contains exactly this many edges and has no triangles.

Proof Architecture

Lemma 1. A complete bipartite graph with parts of sizes $a$ and $b$ contains no triangles and has $ab$ edges; for fixed $a+b=n$, the product $ab$ is maximal when $|a-b|\le1$.

The graph is bipartite, so every cycle has even length; in particular there are no triangles. The product computation is elementary.

Lemma 2. In a triangle-free graph, the neighbors of any vertex are pairwise nonadjacent.

If two neighbors of a vertex were adjacent, together with that vertex they would form a triangle.

Lemma 3. Let $G$ be a triangle-free graph on $n$ vertices, let $v$ have maximum degree $d$, and let $e(G)$ be the number of edges. Then

$$e(G)\le d(n-d)+e(H),$$

where $H$ is the graph obtained by deleting $v$ and all its neighbors.

Every edge either lies in $H$ or is incident with at least one deleted vertex. Counting such edges via the degree bound gives the estimate.

Lemma 4. If $m=n-d-1$, then

$$d(n-d)+\frac{m^2}{4}\le \frac{n^2}{4}.$$

This reduces to a simple quadratic identity.

The hardest direction is the upper bound. Lemma 3 is the critical structural step.

Solution

Represent the given configuration by a graph $G$. The vertices of $G$ are the points $A_1,\dots,A_n$, and two vertices are joined by an edge whenever the corresponding segment is drawn.

Since no three given points are collinear, three vertices determine a triangle in the geometric sense exactly when the three corresponding edges are present. Thus the condition of the problem is equivalent to saying that $G$ contains no triangle.

We first construct a triangle-free graph with many edges.

Split the $n$ vertices into two sets of sizes

$$a=\left\lfloor\frac n2\right\rfloor,\qquad b=\left\lceil\frac n2\right\rceil.$$

Join every vertex of the first set to every vertex of the second set, and draw no other edges.

This is the complete bipartite graph $K_{a,b}$. Every edge joins vertices from different parts, so a triangle cannot occur. The number of edges equals

$$ab = \left\lfloor\frac n2\right\rfloor \left\lceil\frac n2\right\rceil = \left\lfloor\frac{n^2}{4}\right\rfloor.$$

Hence

$$e_{\max}\ge \left\lfloor\frac{n^2}{4}\right\rfloor.$$

It remains to prove that no triangle-free graph on $n$ vertices has more edges.

We proceed by induction on $n$.

For $n=1$ and $n=2$, the statement is immediate.

Assume that every triangle-free graph on fewer than $n$ vertices has at most $\lfloor m^2/4\rfloor$ edges, where $m$ is its number of vertices.

Let $G$ be a triangle-free graph on $n$ vertices. Let $v$ be a vertex of maximum degree, and denote its degree by $d$.

Because $G$ is triangle-free, any two neighbors of $v$ are nonadjacent. Otherwise, if neighbors $x$ and $y$ were adjacent, the edges $vx$, $vy$, and $xy$ would form a triangle.

Delete $v$ and all its $d$ neighbors. Let $H$ be the remaining graph. The graph $H$ has

$$m=n-d-1$$

vertices.

Consider the edges of $G$.

Every edge not belonging to $H$ has at least one endpoint among the deleted vertices. There are $d+1$ deleted vertices. Since $v$ has maximum degree $d$, every deleted vertex has degree at most $d$. Consequently the sum of degrees of all deleted vertices is at most

$$(d+1)d.$$

Each edge not in $H$ contributes at least $1$ to this degree sum. Therefore the number of edges not in $H$ is at most

$$(d+1)d-d=d^2.$$

Indeed, among these edges are exactly the $d$ edges incident with $v$, and all remaining such edges are counted at most once by the degrees of the $d$ neighbors.

Hence

$$e(G)\le d^2+e(H).$$

Using the inductive hypothesis,

$$e(H)\le \left\lfloor\frac{m^2}{4}\right\rfloor.$$

Thus

$$e(G)\le d^2+\left\lfloor\frac{(n-d-1)^2}{4}\right\rfloor.$$

To compare this with $\frac{n^2}{4}$, write $m=n-d-1$. Then

$$d^2+\frac{m^2}{4} = d^2+\frac{(n-d-1)^2}{4}.$$

Multiplying by $4$ and subtracting from $n^2$ gives

\begin{align*}

n^2-4d^2-(n-d-1)^2

&=

n^2-4d^2-\bigl(n^2-2n(d+1)+(d+1)^2\bigr)\

&=

2n(d+1)-5d^2-2d-1\

&=

(d-1)^2+4d(n-d).

\end{align*}

Since $0\le d\le n-1$, the right-hand side is nonnegative. Therefore

$$d^2+\frac{(n-d-1)^2}{4}\le\frac{n^2}{4}.$$

Hence

$$e(G)\le \frac{n^2}{4}.$$

Because $e(G)$ is an integer,

$$e(G)\le \left\lfloor\frac{n^2}{4}\right\rfloor.$$

The lower bound and upper bound coincide. Therefore the greatest possible number of segments is

$$\boxed{\left\lfloor\frac{n^2}{4}\right\rfloor}.$$

Equality is attained by the complete bipartite graph with parts of sizes $\lfloor n/2\rfloor$ and $\lceil n/2\rceil$.

Verification of Key Steps

The first delicate point is the transition from geometry to graph theory. If three vertices are joined pairwise, the corresponding segments form a geometric triangle only because no three given points are collinear. Without that hypothesis, three pairwise connected collinear points would produce a graph-theoretic triangle but not a geometric one.

The second delicate point is proving that the neighbors of the chosen vertex $v$ are independent. Suppose $x$ and $y$ are neighbors of $v$. If $xy$ were an edge, then the three edges $vx$, $vy$, and $xy$ would exist simultaneously, producing a triangle. Hence no such edge can occur.

The third delicate point is the final inequality. A careless argument might estimate the number of deleted edges by $(d+1)d$, double-counting many edges and obtaining a bound too weak to finish the proof. The correct estimate is $d^2$, obtained from the fact that exactly $d$ deleted edges are incident with $v$, while every other deleted edge is incident with one of the $d$ neighbors, each having degree at most $d$.

Alternative Approaches

A different proof uses the theorem of Mantel. For a triangle-free graph on $n$ vertices, choose an edge $uv$. Every other vertex can be adjacent to at most one of $u$ and $v$, otherwise a triangle would arise. Summing suitable inequalities over all edges yields

$$e\le \frac{n^2}{4}.$$

The extremal graphs are precisely complete bipartite graphs with parts as equal as possible.

The inductive approach is preferable here because it requires only elementary graph-theoretic ideas. The structure of the neighborhood of a maximum-degree vertex immediately exploits the absence of triangles, and the induction leads directly to the sharp bound.