Name the vertices $v_1,v_2,...,v_20$. We know that $200=2|E|=\sum_{i=1}^{20}d(v_i)$. Take an edge $v_iv_j$ where $1\le i<j\le 20$. There are $d(v_i)-1$ edges connected to $v_i$ other than $v_iv_j$ and $d(v_j)-1$ edges connected to $v_j$ other than $v_iv_j$. So there are $$|E|-1-(d(v_i)-1)-(d(v_j)-1)=|E|+1-d(v_i)-d(v_j)$$edges disjoint with $v_iv_j$. Because each pairs of edges is counted twice in the sum $$\sum_{1\le i<j\le 20}(|E|+1-d(v_i)-d(v_j))$$we have by our assumption $4050\cdot 2=\sum_{1\le i<j\le 20}(|E|+1-d(v_i)-d(v_j))={20\choose 2}\cdot (|E|+1)-19\sum_{i=1}^{20}d(v_i)=190\cdot (100+1)-19\cdot 200=15390$ And so I say what's going on with this problem?

The problem is correct, and it is easy to get trapped in the counting step. For completeness, here is my proof: Let the graph be $G=(V,E)$ with $|V|=20$ and $|E|=100$, and let $d_1,\dots,d_{20}$ be the degrees of each vertex. Clearly, $\sum_{v=1}^{20} d_v = 2|E|=200$. We now count the total number of ways this job can be done. First, let us select a vertex $v$, and from $v$, we can select one of its $d_v$ neighbours. Having selected $v$ and $v'\in\mathcal{N}_v$ (where $|\mathcal{N}_v|=d_v$), the number of remaining choices for the second edge is $100-(d_v+d_{v'}-1)=101-d_v-d_{v'}$. This makes us arrive at the object: $$ \sum_{v=1}^{20}\sum_{v'\in\mathcal{N}_v} (101-d_v-d_{v'}). $$Note that, this object counts each unordered pairs $(e,f)$ of disjoint edges four times. Thus, $$ \sum_{v=1}^{20}\sum_{v'\in\mathcal{N}_v} (101-d_v-d_{v'}) = 16200. $$Note also that, $$ \sum_{v=1}^{20}\sum_{v'\in\mathcal{N}_v} (101-d_v-d_{v'}) = 101\sum_{v=1}^{20}d_v - 2\sum_{v=1}^{20}d_v^2, $$yielding that, $$ \sum_{v=1}^{20}d_v^2 = 2000. $$Now, using Cauchy-Schwarz inequality, we also have, $$ 20\sum_{v=1}^{20}d_v^2\geqslant \left(\sum_{v=1}^{20}d_v\right)^2 = 40000, $$implying $\sum_{v=1}^{20}d_v^2\geqslant 2000$. Thus, we have an equality in Cauchy-Schwarz, which holds if and only if $d_1=\cdots=d_{20}=10$, that is, if and only if the graph is regular.

Sketch of my in-test handwritten solution: Note that double counting the number of non-disjoint pairs of edges gives: \[900 = \binom{100}{2}-4050 = \sum_{i=1}^{20} \binom{\text{deg } v_i}{2} \geq 20 \cdot \binom{\frac{1}{20}\sum \text{deg } v_i}{2} = 20\cdot \binom{10}{2}=900\]Since this inequality is sharp, all $\text{deg }v_i$ must be equal due to equality case of jensen's, so we are done.

The number of ways to choose a pair of disjoint edges is equal to $\binom{100}{2} - \sum\binom{d_i}{2}$. As $\sum d_i$ is constant at $200$, Jensen's yields that $\sum\binom{d_i}{2} \ge 20\binom{10}{2} = 900$, with equality only holding if the graph is regular. Thus, $\binom{100}{2} - \sum\binom{d_i}{2} \le 4050$. As we are working with the equality case, the graph must be regular.

AwesomeYRY wrote: Sketch of my in-test handwritten solution: AwesomeYRY you are my favorite iranian alive in 2002 If $d_i$ is the degree of the $i$-th vertex, the the number of ways to choose a pair of disjoint edges is $$\binom{100}{2}-\sum_{i=1}^{20} \binom{d_i}{2}\leq \binom{100}{2}-20\binom{10}{2}=4050$$by Jensen's, with equality only when all the $d_i$ are equal. $\blacksquare$

Count complementarily. The number of edge-pairs that are incident on common vertex is exactly $\binom{d_i}2$. So, the number of "bad pairs" is exactly \[\sum_{i}\binom{d_i}2=\frac12\left(\sum_{i}d_i^2-\sum_{i}d_i\right)\geq\frac{e(2e-n)}{n}\](Cauchy-Schwarz) So, there are at most $\binom{e}{2}-\frac{e(2e-n)}{n}=\frac{e}{2n}\left(e(n-4)+n\right)$ good pairs. Plug $e=100$ and $n=20$ and notice that there are exactly $\frac{e}{2n}\left(e(n-4)+n\right)$ good pairs. So, "equality" holds in Cauchy-Schwarz and $d_i$ are all equal. So, graph is regular. $\blacksquare$

We have that the number of ways to choose a pair of disjoint edges is equal to \[\frac{100^2-\sum_{i\in V}d(i)(d(i)-1)}{2}\]Where $V$ is the set of vertices and $d(i)$ is the degree of $i$, thus if we let $f$ be $n(n-1)$ as $f$ is convex we get: \[f(\frac{\sum_{i\in V}d(i)}{20})\leq \frac{\sum_{i\in V} f(i)}{20}\]With equality only holding when all $i$ are equal we get that the graph is regular.

N3bula wrote: We have that the number of ways to choose a pair of disjoint edges is equal to \[\frac{100\cdot 101-\sum_{i\in V}d(i)(d(i)-1)}{2}\]Where $V$ is the set of vertices and $d(i)$ is the degree of $i$, thus if we let $f$ be $n(n-1)$ as $f$ is convex we get: \[f(\frac{\sum_{i\in V}d(i)}{20})\leq \frac{\sum_{i\in V} f(i)}{20}\]With equality only holding when all $i$ are equal we get that the graph is regular.

Note that the number of ways to choose two non-disjoint edges is given by \[\sum_{v \in V} {\deg v \choose 2} \geq |V|{2|E|/|V| \choose 2} = 900\]by Jensen's inequality. However in fact there are ${100 \choose 2} - 4050 = 900$ ways to pick two non-disjoint edges, so equality holds in the expression, i.e. $\deg v$ is constant and the graph is regular.

There are $\binom{100}{2} = 4950$ ways to choose $2$ distinct edges, the condition then forces that there are $900$ ways to choose two distinct but joint edges, this implies $900 = \sum \binom{d_i}{2}$ where $d_i$ is the degree of the $i$th vertex. However, we can establish $\sum \binom{d_i}{2} \ge 20 \binom{\frac{1}{20} \sum d_i}{2} = 20 \binom{10}{2} = 900$, by Jensen, so by Jensen equality case we must have all $d_i$ equal as desired.