Maths Olympiad Prep

Library / /89 of 97

Combinatorics Difficulty 8.7 Shortlist Find the answer

Let GG be a simple graph with 100 vertices such that for each vertice uu, there exists a vertice vN(u)v \in N \left ( u \right ) and N(u)N(v)=\o N \left ( u \right ) \cap N \left ( v \right ) = \o . Try to find the maximal possible number of edges in GG. The N(.) N \left ( . \right ) refers to the neighborhood.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let G G be a simple graph with 100 vertices such that for each vertex u u , there exists a vertex vN(u) v \in N(u) and N(u)N(v)= N(u) \cap N(v) = \emptyset . We aim to find the maximal possible number of edges in G G .

We claim that the maximal number of edges is 3822 \boxed{3822} .

To prove this, we consider the structure of the graph. Call an edge "good" if it is not part of any triangles. The problem condition implies that every vertex is incident to some good edge. Consider a minimal set S S of good edges such that every vertex is incident to some edge in S S . We claim that S S is a collection of disjoint star graphs. There are no cycles in S S , as removing one edge in that cycle from S S would still leave a valid set. Similarly, there are no paths of length 3 or more, since removing a middle edge from the path would also leave a valid set.

Suppose the stars in S S have sizes a1,a2,,am a_1, a_2, \ldots, a_m , where a star of size a a is a vertex connected to a a leaves. We have:
i=1m(ai+1)=100. \sum_{i=1}^m (a_i + 1) = 100.

We cannot add any edges within the vertices of any given star, as that would create a triangle involving some edge of the star. We now estimate the number of edges between different stars.

Lemma: Suppose we have two stars of sizes a a and b b . We add a set E E of edges between them such that none of the edges of the stars is part of a triangle. Then, Eab+1 |E| \leq ab + 1 .

Proof: Suppose α \alpha is the root of the a a -star and x x is some leaf of the a a -star. Let da d_a be the number of edges of E E incident to α \alpha , and let dx d_x be the number of edges of E E incident to x x . We claim that:
1ada+dxb+1a. \frac{1}{a}d_a + d_x \leq b + \frac{1}{a}.
Summing this over all leaves x x finishes the proof. Each vertex in the b b -star can be connected to only one of α \alpha or x x , so da+dxb+1 d_a + d_x \leq b + 1 . However, x x cannot be connected to both the root and a leaf of the b b -star, so dxb d_x \leq b . Thus,
1ada+dx1a(b+1)+a1ab=b+1a, \frac{1}{a}d_a + d_x \leq \frac{1}{a}(b + 1) + \frac{a - 1}{a}b = b + \frac{1}{a},
as desired. \blacksquare

Thus, the total number of edges is at most:
i=1mai+1i<jm(1+aiaj). \sum_{i=1}^m a_i + \sum_{1 \leq i < j \leq m} (1 + a_i a_j).
Letting bi=ai+1 b_i = a_i + 1 , we see that the number of edges is at most:
10022(100m)(m2)12i=1mbi2. \frac{100^2}{2} - (100 - m)(m - 2) - \frac{1}{2} \sum_{i=1}^m b_i^2.
It suffices now to show that the maximum of the above expression over all sequences (b1,,bm) (b_1, \ldots, b_m) that sum to 100 and have bi2 b_i \geq 2 is 3822. Since bi2 b_i \geq 2 for all i i , we have 1m50 1 \leq m \leq 50 .

By Cauchy-Schwarz, we have:
i=1mbi21002m, \sum_{i=1}^m b_i^2 \geq \frac{100^2}{m},
so:
10022(100m)(m2)121002m10022(100m)(m2)121002m. \frac{100^2}{2} - (100 - m)(m - 2) - \frac{1}{2} \frac{100^2}{m} \leq \frac{100^2}{2} - (100 - m)(m - 2) - \frac{1}{2} \frac{100^2}{m}.
It is not hard to see that:
f(m):=10022(100m)(m2)121002m<3822 f(m) := \frac{100^2}{2} - (100 - m)(m - 2) - \frac{1}{2} \frac{100^2}{m} < 3822
for m[1,50]{8} m \in [1, 50] \setminus \{8\} . We see f(8)=3823 f(8) = 3823 , so if there is a graph with more than 3822 edges, then equality is achieved for our Cauchy-Schwarz bound, so all the bi b_i are equal to 100/8 100/8 , which is not an integer. Therefore, we have:
10022(100m)(m2)12i=1mbi23822, \frac{100^2}{2} - (100 - m)(m - 2) - \frac{1}{2} \sum_{i=1}^m b_i^2 \leq 3822,
as desired. Equality is achieved at (b1,,b8)=(12,12,12,12,13,13,13,13) (b_1, \ldots, b_8) = (12, 12, 12, 12, 13, 13, 13, 13) .

The equality case is four 11-stars and four 12-stars, with all the roots of the stars connected to each other, and the 8 groups of sizes (11,11,11,11,12,12,12,12) (11, 11, 11, 11, 12, 12, 12, 12) connected to make the complete 8-partite graph K11,11,11,11,12,12,12,12 K_{11, 11, 11, 11, 12, 12, 12, 12} .

Thus, the maximal possible number of edges in G G is 3822 \boxed{3822} .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.