Направленный граф с максимальной степенью вершины

Я пытался рассмотреть несколько приложений сетевого потока, когда я натолкнулся на эту проблему:

Начнем с ориентированного графа, G = (V, E) . Нам нужно добавить больше ребер к графу так, чтобы у нас было \ forall u, v \ in V, e = (u -> v) или e = (v -> u), но не оба сразу . т.е. мы хотим добавить больше ребер в граф, чтобы каждая пара вершин в графе была связана друг с другом (либо с исходящим, либо с входящим ребром, но не с обоими). Итак, всего у нас будет | V || V-1 | / 2 ребер. При построении этого графа нам необходимо убедиться, что степень данной вершины, скажем w , является максимальной среди всех вершин графа (если это возможно, с учетом исходного графа). Обратите внимание, что мы не можем изменить ориентацию ребер в исходном графе.

Я пытаюсь решить эту проблему, используя сетевой поток, построив сеть без вершины w (и с 2 новыми вершинами для источника s и стока t). Но я не уверен, как представить пропускную способность и направление потока в новом графе, чтобы упростить задачу до сетевого потока, чтобы найти ориентацию ребер в графе.Может, то, что я делаю, не так, но я просто написал, если кто-то может получить от этого подсказку.