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$ – Mahdi Cheraghchi Aug 13 '20 at 18:12
  • $\begingroup$ @MahdiCheraghchi Yes! $\endgroup$ – Freiburger0 Aug 13 '20 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 '20 at 18:31

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 '20 at 15:42
  • $\begingroup$ I think this response should be accepted, as it completely answers the question. $\endgroup$ – Mahdi Cheraghchi Sep 7 '20 at 20:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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