Нет.

Доказательство. Пусть в графе на 800 вершинах выполнено требование: для любого разбиения на две части по 400 вершин число рёбер внутри первой части равно числу рёбер внутри второй. Для каждого множества S размера 400 положим x_v = +1, если v ∈ S, и xv = −1, если v ∉ S. Тогда для любого такого x
e(S) − e(S^c) = 1/2 · ∑{v} xv deg(v).
По условию левая часть равна 0 для всех таких x, значит ∑{v} x_v deg(v)=0 для всех векторов x с 400 плюсами и 400 минусами.

Возьмём любые два различных вершины u и v и выберем вектор x с x_u=+1, x_v=−1 и любыми 399 другими плюсами и 399 минусами на оставшихся вершинах (такой x существует). Поменяв местами знаки у u и v, получим второй допустимый вектор x'. Для x и x' имеем ∑ x_v deg(v)=0 и ∑ x'_v deg(v)=0; вычитая, получаем deg(u)=deg(v). Значит все вершины имеют одинаковую степень k, т.е. граф регулярен.

Тогда 2m = 800·k, следовательно m = 400·k — обязательно кратно 400. Число 3000 не кратно 400, поэтому такой граф не существует. Таким образом король не сможет построить ровно 3000 дорог.