Let be a simple graph with 100 vertices such that for each vertice , there exists a vertice and . Try to find the maximal possible number of edges in . The refers to the neighborhood.
Solution
Let be a simple graph with 100 vertices such that for each vertex , there exists a vertex and . We aim to find the maximal possible number of edges in .
We claim that the maximal number of edges is .
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 of good edges such that every vertex is incident to some edge in . We claim that is a collection of disjoint star graphs. There are no cycles in , as removing one edge in that cycle from 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 have sizes , where a star of size is a vertex connected to leaves. We have:
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 and . We add a set of edges between them such that none of the edges of the stars is part of a triangle. Then, .
Proof: Suppose is the root of the -star and is some leaf of the -star. Let be the number of edges of incident to , and let be the number of edges of incident to . We claim that:
Summing this over all leaves finishes the proof. Each vertex in the -star can be connected to only one of or , so . However, cannot be connected to both the root and a leaf of the -star, so . Thus,
as desired.
Thus, the total number of edges is at most:
Letting , we see that the number of edges is at most:
It suffices now to show that the maximum of the above expression over all sequences that sum to 100 and have is 3822. Since for all , we have .
By Cauchy-Schwarz, we have:
so:
It is not hard to see that:
for . We see , so if there is a graph with more than 3822 edges, then equality is achieved for our Cauchy-Schwarz bound, so all the are equal to , which is not an integer. Therefore, we have:
as desired. Equality is achieved at .
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 connected to make the complete 8-partite graph .
Thus, the maximal possible number of edges in is .