Indivisible

Research note: I checked the Codeforces statement and the official tutorial page. The tutorial text is currently blank in the HTML, but the visible accepted construction uses the same skeleton: balanced cyclic graphs on odd active vertex counts, plus a complement trick for dense even cases. The statement above is still the canonical source.

Let

$D(S)=\sum_{v\in S}\deg(v)$.

The total degree sum is $2m$, so the vertices can be split into two equal-degree-sum parts iff there exists some subset $S$ with $D(S)=m$. So our job is to construct a simple graph whose degree multiset has no subset sum $m$.

A few tiny edge counts are impossible. The exceptional values are

$m\in\{1,2,4,6\}.$

For these, every simple graph with $m$ edges has some subset of vertices with degree sum $m$. This is a small finite lemma: after deleting isolated vertices there are at most $2m\le 12$ relevant vertices, and checking the graphical degree partitions of $2m$ gives a subset sum $m$ every time. This is not the clever part; it is just the annoying pocket tax.

There is a companion dense-version exception. If $n$ is even and the number of missing edges from $K_n$ is in

$\{0,1,2,4,6\},$

then no answer exists. For a missing graph $H$ with that many edges, the same finite check, padded with isolated vertices, gives a subset of exactly $n/2$ vertices whose degree sum inside $H$ is the number of missing edges. In the complement graph, that subset has exactly half the total degree sum.

Now for the construction.

First, isolated vertices are harmless. If we can build a beautiful graph on $N\le n$ vertices with $m$ edges, we just leave the other $n-N$ vertices isolated.

Odd Active Vertex Count

Assume the active vertex count $N$ is odd. We reduce $N$ by $2$ while

$m\le \binom{N-2}{2}.$

After this reduction,

$\binom{N-2}{2}<m\le \binom{N}{2}.$

Write

$2m=qN+r,\qquad 0\le r<N.$

We want degrees

• $r$ vertices of degree $q+1$,
• $N-r$ vertices of degree $q$.

The parity works automatically because $N$ is odd, so $q$ and $r$ have the same parity.

If $q$ is even, add all cyclic edges of distances

$1,2,\ldots,\frac q2.$

This gives a $q$-regular graph. Then add $r/2$ more edges of cyclic distance $\lfloor N/2\rfloor$. These edges are new and distinct, and they increase exactly $r$ degrees by $1$.

If $q$ is odd, start from the cyclic graph of degree $q+1$, built using distances

$1,2,\ldots,\frac{q+1}{2}.$

Then skip/delete $(N-r)/2$ disjoint distance-$1$ edges. This lowers exactly $N-r$ vertices by $1$, leaving the same desired degree multiset.

The edge count is exactly

$\frac{qN+r}{2}=m.$

Why is this degree sequence indivisible? Suppose a subset has $k$ vertices and contains $x$ of the high-degree vertices. Its degree sum is

$qk+x.$

For $N\ge 11$, the reduction above implies $q>(N-1)/2$. Since $N$ is odd, one side of any partition has more vertices. Even if every vertex on the larger side has degree $q$ and every vertex on the smaller side has degree $q+1$, the larger side still has larger degree sum:

$q\cdot\frac{N+1}{2}>(q+1)\cdot\frac{N-1}{2}.$

So equality is impossible.

The boundary cases with small $N$ are where this clean inequality can become tight. The only dangerous reachable values are $m=6$ and $m=12$. We already declared $m=6$ impossible. For $m=12$, we use a special graph on vertices $1\ldots 6$: take every edge touching at least one of $4,5,6$. Its degrees are

$3,3,3,5,5,5.$

A subset sum of $12$ would require

$3a+5b=12,\qquad 0\le a,b\le 3,$

which has no solution. So $m=12$ is safely constructible.

Even Vertex Count

Now suppose $n$ is even.

If

$m\le \binom{n-1}{2},$

we recursively build the graph on $n-1$ vertices and leave vertex $n$ isolated.

Otherwise the graph is dense. Let

$r=\binom n2-m$

be the number of missing edges. Here $r<n-1$. If $r\in\{0,1,2,4,6\}$, the dense exception says no solution exists.

Otherwise, recursively build a beautiful graph $H$ with $r$ edges on vertices $1\ldots n-1$. Then output

$K_n\setminus E(H).$

Why does complementing work? For a subset $S$, let $h(S)$ be the sum of degrees inside the missing graph $H$ over vertices of $S$; vertex $n$ has degree $0$ in $H$. In the complement graph $G$,

$D_G(S)=(n-1)|S|-h(S).$

If $D_G(S)=m=\binom n2-r$, then

$h(S)-r=(n-1)\left(|S|-\frac n2\right).$

But $0\le h(S)\le 2r$, so

$|h(S)-r|\le r<n-1.$

The right side is a multiple of $n-1$, so it must be $0$. Therefore $|S|=n/2$ and $h(S)=r$. But $h(S)=r$ is exactly a forbidden half-degree subset in $H$. Contradiction.

Thus the complement graph is beautiful.

The construction outputs exactly $m$ edges. Its running time is $O(n+m\log m)$ per test because of sorting the missing-edge list in the complement step, and the total constraints easily fit. Memory usage is $O(m)$.