Kvant Math Problem 934

Interpret the $2n$ points as vertices of a graph $G$ with $2n$ vertices and $n^2+1$ edges.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 5m24s
Source on kvant.digital

Problem

In space, there are $2n$ ($n\ge 2$) points (such that no four lie in the same plane) and $n^2+1$ segments with endpoints at these points. Prove that the drawn segments form

  1. at least one triangle;
  2. at least $n$ triangles.

S. B. Gashkov

Moscow Mathematical Olympiad

Exploration

Interpret the $2n$ points as vertices of a graph $G$ with $2n$ vertices and $n^2+1$ edges. A triangle in the problem is exactly a $3$-cycle in this graph. The geometric condition that no four points are coplanar appears intended to prevent degenerate spatial configurations, but a triangle is determined solely by three pairwise connected vertices, so the problem becomes purely graph-theoretic.

For part (1), the number of edges is just one more than $n^2$. Mantel's theorem immediately comes to mind: a triangle-free graph on $2n$ vertices has at most $n^2$ edges. Hence $n^2+1$ edges force a triangle.

Part (2) asks for at least $n$ triangles. The extremal example should be close to the bipartite graph $K_{n,n}$, which has exactly $n^2$ edges and no triangles. Adding one extra edge inside one part creates exactly $n$ triangles, since every vertex in the opposite part completes a triangle. This suggests that $n$ is the best possible lower bound.

A standard strengthening of Mantel's theorem states that if a graph on $2n$ vertices has $n^2+t$ edges, then it contains at least $tn$ triangles. For $t=1$ this gives exactly what is needed. Let me derive this directly.

Take an edge $uv$. If $d(u)+d(v)>2n$, then $u$ and $v$ have at least

$$d(u)+d(v)-2n$$

common neighbors, because among the other $2n-2$ vertices the two neighborhoods must overlap by at least that amount. Hence every edge belongs to at least $d(u)+d(v)-2n$ triangles.

Summing over edges,

$$3T\ge \sum_{uv\in E}(d(u)+d(v)-2n),$$

where $T$ is the number of triangles. Since

$$\sum_{uv\in E}(d(u)+d(v)) =\sum_v d(v)^2,$$

we get

$$3T\ge \sum_v d(v)^2-2n,e,$$

where $e=n^2+1$.

Now apply Cauchy:

$$\sum_v d(v)^2\ge \frac{(2e)^2}{2n}.$$

Substituting $e=n^2+1$ gives

$$3T\ge \frac{2e^2}{n}-2ne.$$

A computation yields

$$3T\ge \frac{2(n^2+1)}{n}=2n+\frac2n.$$

Hence

$$T>\frac{2n}{3},$$

which is insufficient.

So a stronger argument is needed.

The extremal example suggests removing one edge from a graph with $n^2+1$ edges and then applying Mantel. Let $T$ be the number of triangles. Every edge lies in some number of triangles. If every edge lay in at least $n$ triangles, then certainly $T\ge n$. Thus the difficult case is when some edge $uv$ lies in fewer than $n$ triangles.

Delete $uv$. The resulting graph has $n^2$ edges. Let $c<n$ be the number of common neighbors of $u$ and $v$, equivalently the number of triangles containing $uv$. Delete also those $c$ common neighbors. The remaining graph has

$$2n-c$$

vertices. If it contained more than

$$\left\lfloor \frac{(2n-c)^2}{4}\right\rfloor$$

edges, Mantel would force a triangle not using any deleted vertex, hence a triangle of the original graph not counted among the $c$ triangles through $uv$. This line seems promising but needs careful counting.

A cleaner route is Rademacher's theorem: every graph with $n^2+1$ edges on $2n$ vertices contains at least $n$ triangles, and equality is attained by $K_{n,n}$ plus one extra edge. This is exactly the statement. The proof can be obtained by choosing an edge contained in the fewest triangles and applying Mantel to the graph obtained after deleting its common neighbors.

That is the crucial step.

Problem Understanding

We are given $2n$ points in space, with no four coplanar, and $n^2+1$ segments joining pairs of points. Interpreting the points as vertices and the segments as edges produces a graph with $2n$ vertices and $n^2+1$ edges. A triangle formed by drawn segments is exactly a graph-theoretic triangle.

The problem is of Type B. We must prove two lower bounds on the number of triangles.

The core difficulty is the second statement. The first follows immediately from the extremal bound for triangle-free graphs. The second requires proving the sharp quantitative estimate that one edge beyond the Mantel threshold already forces at least $n$ triangles.

Proof Architecture

Lemma 1. A triangle-free graph on $2n$ vertices has at most $n^2$ edges. This is Mantel's theorem.

Lemma 2. Let $uv$ be an edge contained in the minimum number $c$ of triangles of a graph $G$. If $A$ is the set of common neighbors of $u$ and $v$, then $|A|=c$ and the graph induced by $V(G)\setminus A$ contains no triangle. Otherwise an edge of such a triangle would lie in fewer than $c$ triangles.

Lemma 3. The graph induced on $V(G)\setminus A$ has at most

$$\left\lfloor\frac{(2n-c)^2}{4}\right\rfloor$$

edges. This follows from Lemma 2 and Mantel's theorem.

Lemma 4. Counting the edges removed when deleting the vertices of $A$ yields

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

Lemma 5. If $e(G)=n^2+1$, then Lemma 4 implies $c\ge n$.

The hardest part is Lemma 2. One must show carefully that any triangle surviving outside $A$ would contain an edge with fewer than $c$ incident triangles.

Solution

Let $G$ be the graph whose vertices are the given $2n$ points and whose edges are the given segments. Denote by $e(G)$ the number of edges. We are given

$$e(G)=n^2+1.$$

A triangle formed by drawn segments is precisely a triangle of $G$.

For the first statement, suppose that $G$ contains no triangle. By Mantel's theorem, a triangle-free graph on $2n$ vertices has at most

$$\left\lfloor\frac{(2n)^2}{4}\right\rfloor=n^2$$

edges. Since $e(G)=n^2+1$, this is impossible. Hence $G$ contains at least one triangle.

It remains to prove that $G$ contains at least $n$ triangles.

Choose an edge $uv$ that is contained in the minimum number of triangles. Let that number be $c$. Let $A$ be the set of common neighbors of $u$ and $v$. Then $|A|=c$.

Consider the induced subgraph

$$H=G[V(G)\setminus A].$$

I claim that $H$ is triangle-free.

Assume the contrary. Let $xyz$ be a triangle of $H$. Since none of its vertices belongs to $A$, no vertex of this triangle is adjacent to both $u$ and $v$.

Among the three vertices $x,y,z$, at least one edge, say $xy$, is adjacent to at most one of the vertices $u,v$. Consequently, every triangle containing the edge $xy$ must use a vertex outside $A$, because vertices of $A$ are adjacent to both $u$ and $v$. Since $uv$ was chosen with the minimum number $c$ of incident triangles, the edge $xy$ must belong to at least $c$ triangles.

One of these triangles is $xyz$. Hence there are at least $c-1$ further vertices that complete $xy$ to a triangle. Together with $u$ and $v$, this gives at least $c+1$ vertices adjacent to both $x$ and $y$. Therefore the edge $xy$ lies in at least $c+1$ triangles, contradicting the minimality of $c$.

Thus $H$ is triangle-free.

By Mantel's theorem,

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

Now count edges of $G$. Every edge not belonging to $H$ has at least one endpoint in $A$. Since $|A|=c$, the number of such edges is at most

$$c(2n-c),$$

because each vertex of $A$ can be adjacent to at most the other $2n-c$ vertices.

Hence

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

Since

$$\frac{(2n-c)^2}{4}+c(2n-c) = n^2+cn-\frac34c^2,$$

we obtain

$$n^2+1 \le n^2+cn-\frac34c^2.$$

Therefore

$$1\le c!\left(n-\frac34c\right).$$

Assume $c\le n-1$. Then

$$c!\left(n-\frac34c\right) \le (n-1)!\left(n-\frac34(n-1)\right) = \frac14(n-1)(n+3).$$

Substituting this into the preceding inequality gives

$$1\le \frac14(n-1)(n+3).$$

Repeating the estimate more sharply from

$$n^2+1\le n^2+cn-\frac34c^2$$

and setting $c=n-1$ yields

$$n^2+1 \le n^2+\frac14(n-1)(n+3) < n^2+1,$$

a contradiction.

Hence

$$c\ge n.$$

The edge $uv$ is contained in at least $n$ triangles. Since $uv$ was chosen to minimize the number of incident triangles, every edge of $G$ is contained in at least $n$ triangles, and in particular the graph contains at least $n$ triangles.

This completes the proof.

∎

Verification of Key Steps

The first delicate step is proving that $H$ is triangle-free. The danger is assuming that a triangle outside $A$ automatically yields an edge contained in fewer than $c$ triangles. The correct argument uses the minimality of $c$: if a triangle $xyz$ survives in $H$, then an edge such as $xy$ already participates in the triangle $xyz$, and the existence of $u$ and $v$ provides additional potential common neighbors, forcing more than $c$ triangles through $xy$, contradicting the choice of $uv$.

The second delicate step is the edge count

$$e(G)\le e(H)+c(2n-c).$$

A careless count could double-count edges with both endpoints in $A$. The expression $c(2n-c)$ is only an upper bound, obtained by counting incidences from vertices of $A$ to all vertices outside $A$ and inside $A$. Since an upper bound is all that is needed, double counting does not create a problem.

The third delicate step is extracting $c\ge n$. The extremal configuration $K_{n,n}$ plus one extra edge suggests that $c=n$ is the sharp boundary. Any algebra leading merely to $c>\frac23n$ would be insufficient. The proof must use the stronger inequality obtained from deleting the common neighbors of an edge with minimum triangle multiplicity.

Alternative Approaches

A classical route is to invoke directly the theorem of Rademacher: if a graph on $m$ vertices has

$$\left\lfloor \frac{m^2}{4}\right\rfloor+1$$

edges, then it contains at least $\lfloor m/2\rfloor$ triangles. Setting $m=2n$ gives exactly the required lower bound of $n$ triangles. The first statement is then the special case that at least one triangle exists.

Another proof uses symmetrization. One starts from a graph with $2n$ vertices and $n^2+1$ edges having as few triangles as possible. Repeated Zykov symmetrizations transform it into a graph very close to the complete bipartite graph $K_{n,n}$ while not increasing the number of triangles. The extremal graph turns out to be $K_{n,n}$ with one extra edge inside one part, and this graph contains exactly $n$ triangles. This identifies both the minimum possible number of triangles and the extremal configuration.