In a simple graph with 300 vertices no two vertices of the same degree are adjacent (boo hoo hoo). What is the maximal possible number of edges in such a graph?
Problem
Source: 2023 Serbia TST Problem 1
Tags: Extremal Graph Theory, ad hoc, Serbia, TST, graph theory, combinatorics
22.05.2023 16:31
gvole wrote: In a simple graph with 300 vertices no two vertices of the same degree are connected. What is the maximal possible number of edges in such a graph? I believe by connected you actually mean adjacent. Because otherwise the answer is $0$ due to the following fact (which can be proved by considering the possible degree sequence assuming the negation). In any simple graph with at least one edge there are two vertices which lie in the same connected component and have the same degree.
22.05.2023 22:15
I claim that the answer is $\frac12 (299 + 298 \cdot 2 + \cdots 276 \cdot 24) = 42550$. Proof of Bound: Notice that we can have at most $k$ vertices with degree $300 - k$, so the bound is obvious. Construction: Label $k$ vertices with the label $k$ for $k$ between $1$ and $24$. Then connect all pairs of vertices except those with the same label. This construction obviously works, so we are done.
23.05.2023 01:28
What a coincidence! See here
23.05.2023 01:36
Great minds think alike hahaha