MaxCut instance with smallest max cut

Question

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?

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.