Let us look at all 4-regular undirected graphs with $n$ nodes and edge weight equals to 1 for all edges. Out of these graphs, I would like to find the MaxCut instance with least number of edges in its optimal solution. How would you construct that?

  • $\begingroup$ So you're asking what's the 4-regular graph on n vertices with the least possible max-cut? $\endgroup$ Aug 13, 2020 at 18:12
  • $\begingroup$ @MahdiCheraghchi Yes! $\endgroup$ Aug 13, 2020 at 18:26
  • 1
    $\begingroup$ Shouldn't it read "with least number of EDGES" instead of "with least number of CUTS"? $\endgroup$
    – Gamow
    Aug 13, 2020 at 18:31

1 Answer 1


Take a clique of size 5 and consider a graph on $n = 5k$ nodes consisting of $k$ copies of this clique. The size of a maximal cut in this graph is $6k = 6n/5$. Indeed, from each copy we can maximally have 6 edges in a cut.

By the following lemma the size of a maximal cut can not be much smaller.

Lemma. In any undirected 4-regular with $n$ nodes there exists a cut with at least $\lceil 6n/5 \rceil$ edges.

More precisely, for $n$ divisible by 5 the answer to your question is exactly $6n/5$. For other $n$ it can be a bit bigger, but only by a $O(1)$ term. Indeed, we can again consider a graph where all but $O(1)$ nodes are paritioned into copies of a 4-regular clique.

Proof. Let $G = (V, E)$ be a 4-regular graph with $n$ nodes and let $(S, T)$ be a maximal cut. For a node $a\in V$ let cut-degree of $a$ be the number of edges containing $a$ and belonging to the cut $(S, T)$. We rely on the following two easily verifiable observations:

  • Observation 1: any node has cut-degree at least 2. Indeed, assume that $a\in V$ has cut degree at most $1$. WLOG, $a\in S$. Then removing $a$ from $S$ and putting it to $T$ would result in a larger cut, contradiction.
  • Observation 2: no edge of the cut connects two nodes with cut-degree 2. Indeed, assume that nodes $a\in S$ and $b\in T$ are adjacent and both have cut-degree 2. Then swapping $a$ and $b$ (putting $a$ to $T$ and $b$ to $S$) would result in a larger cut, contradiction.

Assume that $|S| = s, |T| = t$. Let $x$ be the number of nodes from $S$ with cut-degree 2. Similarly, let $y$ be the number of nodes from $T$ with cut-degree 2.

Let $C$ be the size of the cut $(S, T)$. Note that $C$ equals the sum of cut-degrees over the nodes from $S$. Exactly $x$ nodes from $S$ have cut-degree $2$. By observation 1 all the other nodes from $S$ have cut-degree at least $3$. Hence $$C \ge 2x + 3(s - x) = 3s - x.$$ Applying a similar argument to the set $T$ we obtain: $$C \ge 2y + 3(t - y) = 3t - y.$$ Now, let us sum up the cut-degree over all nodes of $G$ with cut-degree 2. By observation 2 we never count an edge of the cut twice. Hence $$C \ge 2x + 2y.$$ By summing up these 3 inequalities with appropriate weights we obtain: $$5C \ge 2(3s - x) + 2(3t - y) + 2x + 2y = 6(s + t) = 6n.$$ This gives us $C \ge \lceil 6n/5\rceil$. Proof of the Lemma is finished.

  • $\begingroup$ That looks great! $\endgroup$
    – smapers
    Aug 14, 2020 at 15:42
  • $\begingroup$ I think this response should be accepted, as it completely answers the question. $\endgroup$ Sep 7, 2020 at 20:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.