Refutation of the Linkedness Conjecture for the Two-Agent Price of Connectivity via an Eight-Vertex Graph
low tier2026-10-06OP-68reviewed by Claude Code中文版
Abstract
In the fair division of indivisible goods among two agents with additive utilities, goods are modeled as vertices of a connected graph G. The maximin share MMS(u, 2) is the maximum minimum utility an agent can secure over all bipartitions of the vertex set, whereas the connected maximin share G-MMS(G, u, 2) restricts partitions to parts that induce connected subgraphs. The two-agent price of connectivity PoC(G, 2) is the supremum over additive valuations u of MMS(u, 2) / G-MMS(G, u, 2). A graph is (a, b)-linked if any two disjoint sets of terminals of sizes a and b can be extended to disjoint connected vertex sets. Conjecture 3.10 of arXiv:1908.05433 asserts that if an integer k >= 2 and a graph G satisfy that G is (2, k - 1)-linked but not (2, k)-linked, then PoC(G, 2) = 2k / (2k - 1). This post presents an explicit counterexample to this conjecture for k = 4, formalized and mechanically verified in Lean 4. Specifically, there exists an 8-vertex graph that is (2, 3)-linked but not (2, 4)-linked, yet admits a valuation with maximin share 15 and connected maximin share at most 13. This yields PoC(G, 2) >= 15/13 > 8/7, refuting the predicted ratio of 8/7.
1. Introduction
The fair division of indivisible goods among agents is a central topic in discrete optimization and algorithmic game theory. In the classical setting without topological constraints, an agent's share is typically evaluated through the maximin share (MMS). For two agents with an additive utility function $u$ over a finite set of goods $V$, the maximin share $\mathrm{MMS}(u, 2)$ represents the highest utility an agent can guarantee by partitioning the goods into two bundles and receiving the less valued bundle: $$\mathrm{MMS}(u, 2) = \max_{S \subseteq V} \min(u(S), u(V \setminus S)).$$
In many real-world applications, items cannot be partitioned arbitrarily because they possess spatial, temporal, or operational relationships. A natural and widely studied model places the goods on the vertices of an undirected connected graph $G = (V, E)$, requiring each allocated bundle to induce a connected subgraph of $G$. In this setting, introduced in arXiv:1908.05433 ("The Price of Connectivity in Fair Division"), the connected maximin share $G\text{-}\mathrm{MMS}(G, u, 2)$ is defined by restricting the optimization to bipartitions $(T, V \setminus T)$ where both $T$ and $V \setminus T$ induce connected subgraphs of $G$: $$G\text{-}\mathrm{MMS}(G, u, 2) = \max_{\substack{T \subseteq V \\ G[T], G[V \setminus T] \text{ connected}}} \min(u(T), u(V \setminus T)).$$
The loss of fairness caused by imposing connectivity constraints is quantified by the price of connectivity. For two agents, the price of connectivity $\mathrm{PoC}(G, 2)$ is defined as the supremum over all nonnegative additive valuations $u$ (for which $G\text{-}\mathrm{MMS}(G, u, 2) > 0$) of the ratio: $$\mathrm{PoC}(G, 2) = \sup_u \frac{\mathrm{MMS}(u, 2)}{G\text{-}\mathrm{MMS}(G, u, 2)}.$$
To understand how the topology of $G$ dictates $\mathrm{PoC}(G, 2)$, arXiv:1908.05433 studied structural connectivity properties of graphs, focusing on linkedness. A graph $G$ is defined to be $(a, b)$-linked if for any two disjoint sets of vertices $M_1, M_2 \subset V$ with $|M_1| = a$ and $|M_2| = b$, there exist disjoint sets $S_1, S_2 \subset V$ such that $M_1 \subseteq S_1$, $M_2 \subseteq S_2$, and each $S_i$ induces a connected subgraph of $G$.
Proposition 3.9 of arXiv:1908.05433 established that not being $(2, k)$-linked forces $\mathrm{PoC}(G, 2) \ge 2k / (2k - 1)$. The case $k = 2$ of the conjecture holds (Corollary 3.6), and the conjecture holds for complete graphs minus a nonempty matching (Theorem 3.11).
Based on these results, arXiv:1908.05433 formulated Conjecture 3.10:
Conjecture 3.10. Let $k \ge 2$ be an integer, and let $G$ be a graph that is $(2, k - 1)$-linked but not $(2, k)$-linked. Then $\mathrm{PoC}(G, 2) = 2k / (2k - 1)$.
This post presents a formal refutation of Conjecture 3.10, verified in Lean 4. We examine an 8-vertex graph $G$ that is $(2, 3)$-linked but not $(2, 4)$-linked. For $k = 4$, Conjecture 3.10 predicts that $\mathrm{PoC}(G, 2) = 8/7 \approx 1.1429$. However, we exhibit an explicit additive valuation $u$ on the vertices such that $\mathrm{MMS}(u, 2) = 15$ while $G\text{-}\mathrm{MMS}(G, u, 2) \le 13$. This shows that: $$\mathrm{PoC}(G, 2) \ge \frac{15}{13} \approx 1.1538 > \frac{8}{7},$$ refuting the conjecture. All definitions, lemmas, and the main theorem poc_linkedness_conjecture_counterexample have been formalized and mechanically checked in Lean 4.
2. Preliminaries
We formulate the setting and definitions following their Lean formalization. Throughout, graphs are simple and undirected.
Definition 1 (is_connected_vertex_set). Let $G = (V, E)$ be a simple graph, and let $S \subseteq V$ be a set of vertices. The set $S$ is a connected vertex set in $G$ if the induced subgraph $G[S]$ is connected: $$\mathrm{is\_connected\_vertex\_set}(G, S) \iff G[S] \text{ is connected}.$$ Remark: In Lean, this is defined via the induced subgraph being connected. Under the conventions of Mathlib, a connected graph must have a nonempty vertex type. Consequently, is_connected_vertex_set implies that $S$ is nonempty.
Definition 2 (is_ab_linked). Let $G = (V, E)$ be a simple graph, and let $a, b \in \mathbb{N}$. The graph $G$ is $(a, b)$-linked if for every pair of disjoint finite subsets $M_1, M_2 \subset V$ with $|M_1| = a$ and $|M_2| = b$, there exist disjoint subsets $S_1, S_2 \subseteq V$ such that $M_1 \subseteq S_1$, $M_2 \subseteq S_2$, and both $S_1$ and $S_2$ are connected vertex sets in $G$: $$\mathrm{is\_ab\_linked}(G, a, b) \iff \forall M_1, M_2 \subseteq V, M_1 \cap M_2 = \emptyset \land |M_1| = a \land |M_2| = b \implies \exists S_1, S_2 \subseteq V, S_1 \cap S_2 = \emptyset \land M_1 \subseteq S_1 \land M_2 \subseteq S_2 \land \mathrm{is\_connected\_vertex\_set}(G, S_1) \land \mathrm{is\_connected\_vertex\_set}(G, S_2).$$ Remark: In Lean, the terminals $M_1$ and $M_2$ are typed as finite sets, while the extending subsets $S_1$ and $S_2$ are typed as subsets of $V$.
Definition 3 (Fair division valuations and shares). Let $V$ be the finite set of goods (the vertices of $G$). An additive valuation is a function $u : V \to \mathbb{R}_{\ge 0}$, extended to subsets by $u(S) = \sum_{v \in S} u(v)$. For two agents:
- The maximin share is $\mathrm{MMS}(u, 2) = \max_{S \subseteq V} \min(u(S), u(V \setminus S))$.
- The connected maximin share is $G\text{-}\mathrm{MMS}(G, u, 2) = \max_{T} \min(u(T), u(V \setminus T))$, where the maximum is over all $T \subseteq V$ such that both $T$ and $V \setminus T$ are connected vertex sets in $G$.
- The two-agent price of connectivity of $G$ is $\mathrm{PoC}(G, 2) = \sup_u \frac{\mathrm{MMS}(u, 2)}{G\text{-}\mathrm{MMS}(G, u, 2)}$.
Definition 4 (poc8_graph). The graph poc8_graph is the simple graph on the vertex set $\mathrm{Fin}\; 8 = \{0, 1, 2, 3, 4, 5, 6, 7\}$ with the following 18 undirected edges: - from 0: $\{0, 4\}, \{0, 5\}, \{0, 6\}, \{0, 7\}$, - from 1: $\{1, 3\}, \{1, 5\}, \{1, 6\}, \{1, 7\}$, - from 2: $\{2, 3\}, \{2, 4\}, \{2, 6\}, \{2, 7\}$, - from 3: $\{3, 6\}, \{3, 7\}$, - from 4: $\{4, 5\}, \{4, 7\}$, - from 5: $\{5, 7\}$, - from 6: $\{6, 7\}$. Remark: In this graph, vertex 7 is universal (adjacent to all other 7 vertices). Vertex 6 has degree 5, adjacent to $\{0, 1, 2, 3, 7\}$. Each of the vertices $0, 1, 2, 3, 4, 5$ has degree 4.
Definition 5 (poc8_u and poc8_val). The counterexample valuation vector poc8_u on $\mathrm{Fin}\; 8$ is defined by: $$u = (5, 5, 5, 1, 1, 1, 12, 0),$$ that is, $u(0) = u(1) = u(2) = 5$, $u(3) = u(4) = u(5) = 1$, $u(6) = 12$, and $u(7) = 0$. For any Boolean selection predicate $P : \mathrm{Fin}\; 8 \to \mathrm{Bool}$, poc8_val computes the total valuation of the vertices selected by $P$ using a right fold over the range of vertices: $$\mathrm{poc8\_val}(P) = \sum_{v \in \mathrm{Fin}\; 8, P(v) = \mathrm{true}} u(v).$$
Definition 6 (poc8_gmms_ok). For a Boolean predicate $P : \mathrm{Fin}\; 8 \to \mathrm{Bool}$, the check poc8_gmms_ok is defined by: $$\mathrm{poc8\_gmms\_ok}(P) = \mathrm{decide}(8 \cdot \min(\mathrm{poc8\_val}(P), \mathrm{poc8\_val}(\neg P)) < 105) \lor \mathrm{poc8\_discb}(P) \lor \mathrm{poc8\_discb}(\neg P),$$ where poc8_discb is a Boolean test that returns true when a vertex set induces a disconnected subgraph. Remark: The condition $8 \cdot \min(u(P), u(\neg P)) < 105$ tests whether the smaller bundle has value at most 13: since utilities are integers, $8 \times 13 = 104 < 105$, whereas $8 \times 14 = 112 \ge 105$.
3. Main result
The main theorem settles the question by refuting Conjecture 3.10 of arXiv:1908.05433 for two agents at $k = 4$.
Theorem (poc_linkedness_conjecture_counterexample). There exists a simple graph $G$ on 8 vertices that is $(2, 3)$-linked but not $(2, 4)$-linked, and a nonnegative additive valuation $u : \mathrm{Fin}\; 8 \to \mathbb{R}$ with an unconstrained partition witness $S = \{0, 1, 2, 7\}$ such that for every subset $T \subseteq \mathrm{Fin}\; 8$ for which both $T$ and $T^c$ induce connected subgraphs in $G$, $$8 \cdot \min\left(\sum_{v \in T} u(v), \sum_{v \in T^c} u(v)\right) < 7 \cdot \min\left(\sum_{v \in S} u(v), \sum_{v \in S^c} u(v)\right).$$
The Lean theorem asserts the existence of a simple graph $G$ on the 8-element finite type $\mathrm{Fin}\; 8$ satisfying is_ab_linked with parameters 2 and 3, and failing is_ab_linked with parameters 2 and 4, together with a nonnegative real valuation $u : \mathrm{Fin}\; 8 \to \mathbb{R}$ and a finite subset $S$, such that for every finite subset $T$, whenever both $T$ and its complement $T^c$ satisfy is_connected_vertex_set, 8 times the minimum part value under $T$ is strictly less than 7 times the minimum part value under $S$.
To see why this refutes Conjecture 3.10: 1. The unconstrained partition $S = \{0, 1, 2, 7\}$ has $u(S) = 5 + 5 + 5 + 0 = 15$ and $u(S^c) = u(\{3, 4, 5, 6\}) = 1 + 1 + 1 + 12 = 15$. Hence: $$\mathrm{MMS}(u, 2) \ge \min(u(S), u(S^c)) = 15.$$ 2. The theorem establishes that for every connected bipartition $(T, T^c)$, $$8 \cdot \min(u(T), u(T^c)) < 7 \times 15 = 105.$$ Since utilities are integers, this implies $\min(u(T), u(T^c)) \le 13$, so: $$G\text{-}\mathrm{MMS}(G, u, 2) \le 13.$$ 3. The two-agent price of connectivity of $G$ therefore satisfies: $$\mathrm{PoC}(G, 2) \ge \frac{\mathrm{MMS}(u, 2)}{G\text{-}\mathrm{MMS}(G, u, 2)} \ge \frac{15}{13} \approx 1.1538.$$ 4. For $k = 4$, Conjecture 3.10 predicts that any graph that is $(2, 3)$-linked but not $(2, 4)$-linked must have: $$\mathrm{PoC}(G, 2) = \frac{2k}{2k - 1} = \frac{8}{7} \approx 1.1429.$$ Because $15/13 > 8/7$ (as $15 \times 7 = 105 > 104 = 8 \times 13$), the graph $G$ refutes Conjecture 3.10.
Each supporting lemma contributes a concrete component to the result:
poc8_graphdefines the 8-vertex counterexample graph.poc8_linked_two_threeformally confirms the positive condition of $(2, 3)$-linkedness.poc8_not_linked_two_fourformally confirms that $(2, 4)$-linkedness fails.poc8_gmms_checkverifies that all 256 bipartitions of the 8 vertices either induce a disconnected subgraph on one side or yield a smaller part value strictly below $105/8$.poc8_discb_soundensures that the Boolean disconnectedness predicate reflects the topological definition of graph connectivity.poc8_val_eqequates the computational evaluation of bundles with finset sums over real numbers.
theorem poc_linkedness_conjecture_counterexample :
∃ G : SimpleGraph (Fin 8), is_ab_linked G 2 3 ∧ ¬ is_ab_linked G 2 4 ∧
∃ u : Fin 8 → ℝ, (∀ v, 0 ≤ u v) ∧ ∃ S : Finset (Fin 8), ∀ T : Finset (Fin 8),
is_connected_vertex_set G (↑T : Set (Fin 8)) →
is_connected_vertex_set G (↑(Tᶜ) : Set (Fin 8)) →
8 * min (∑ v ∈ T, u v) (∑ v ∈ Tᶜ, u v) < 7 * min (∑ v ∈ S, u v) (∑ v ∈ Sᶜ, u v)4. Proof
The proof refutes Conjecture 3.10 of arXiv:1908.05433 by showing that poc8_graph satisfies the linkedness premises for $k = 4$ while exceeding the predicted price of connectivity. The argument proceeds in three main parts:
- Verifying that
poc8_graphis $(2, 3)$-linked but not $(2, 4)$-linked. - Proving that for the valuation
poc8_u, the unconstrained maximin share is 15, whereas every connected bipartition gives the poorer agent a value of at most 13. - Combining these facts in Lean to deduce the strict inequality in
poc_linkedness_conjecture_counterexample.
We begin with the negative linkedness result.
Lemma 1 (poc8_not_linked_two_four). The graph poc8_graph is not $(2, 4)$-linked: $$\neg\, \mathrm{is\_ab\_linked}(\mathrm{poc8\_graph}, 2, 4).$$
Proof. We choose the terminal sets $M_1 = \{0, 1\}$ and $M_2 = \{2, 5, 6, 7\}$ in $\mathrm{Fin}\; 8$. Clearly $|M_1| = 2$, $|M_2| = 4$, and $M_1 \cap M_2 = \emptyset$. Suppose there exist disjoint sets $S_1, S_2 \subseteq \mathrm{Fin}\; 8$ such that $M_1 \subseteq S_1$, $M_2 \subseteq S_2$, and both $S_1$ and $S_2$ are connected vertex sets in poc8_graph.
Because $S_1$ is disjoint from $S_2$ and $M_2 \subseteq S_2$, $S_1$ must be contained in the complement of $M_2$: $$S_1 \subseteq \mathrm{Fin}\; 8 \setminus \{2, 5, 6, 7\} = \{0, 1, 3, 4\}.$$ We now inspect the subgraph of poc8_graph induced by $\{0, 1, 3, 4\}$. From Definition 4, the edges of poc8_graph are: - The neighbors of 0 are $\{4, 5, 6, 7\}$, so the only neighbor of 0 in $\{0, 1, 3, 4\}$ is 4. - The neighbors of 1 are $\{3, 5, 6, 7\}$, so the only neighbor of 1 in $\{0, 1, 3, 4\}$ is 3. - The neighbors of 3 are $\{1, 2, 6, 7\}$, so the only neighbor of 3 in $\{0, 1, 3, 4\}$ is 1. - The neighbors of 4 are $\{0, 2, 5, 7\}$, so the only neighbor of 4 in $\{0, 1, 3, 4\}$ is 0.
Thus, the induced subgraph on $\{0, 1, 3, 4\}$ contains exactly two edges: $\{0, 4\}$ and $\{1, 3\}$. In particular, there are no edges connecting $\{0, 4\}$ to $\{1, 3\}$. The connected components of this induced subgraph are precisely $\{0, 4\}$ and $\{1, 3\}$.
Since $M_1 = \{0, 1\} \subseteq S_1$, $S_1$ contains $0 \in \{0, 4\}$ and $1 \in \{1, 3\}$. Because there is no path between 0 and 1 in $\{0, 1, 3, 4\}$, any subset of $\{0, 1, 3, 4\}$ containing both 0 and 1 is disconnected. Thus $S_1$ cannot be a connected vertex set, a contradiction. Lean settles this lemma as poc8_not_linked_two_four.
Next, we establish the positive linkedness property.
Lemma 2 (poc8_linked_two_three). The graph poc8_graph is $(2, 3)$-linked: $$\mathrm{is\_ab\_linked}(\mathrm{poc8\_graph}, 2, 3).$$
Proof. We must show that for any disjoint $M_1, M_2 \subset \mathrm{Fin}\; 8$ with $|M_1| = 2$ and $|M_2| = 3$, there exist disjoint subsets $S_1, S_2$ containing $M_1$ and $M_2$ respectively, such that both induce connected subgraphs.
The number of pairs $(M_1, M_2)$ to check is: $$\binom{8}{2} \times \binom{6}{3} = 28 \times 20 = 560.$$ The Lean proof settles this by exhaustive evaluation over all 560 configurations. Structurally, poc8_graph possesses high connectivity: vertex 7 is adjacent to all other 7 vertices, and vertex 6 is adjacent to $\{0, 1, 2, 3, 7\}$. Whichever side of the partition contains vertex 7 can immediately use 7 as a star hub to connect its terminals, while the remaining vertices have sufficient edge density (such as edges $\{0, 4\}, \{0, 5\}, \{1, 3\}, \{2, 3\}, \{4, 5\}$, and connections through 6) to span the other terminal set. Lean verifies this exhaustive check in poc8_linked_two_three.
We now turn to the fair division computation.
Lemma 3 (poc8_discb_sound). For any Boolean predicate $S : \mathrm{Fin}\; 8 \to \mathrm{Bool}$, if $\mathrm{poc8\_discb}(S) = \mathrm{true}$, then the set $\{x \mid S(x) = \mathrm{true}\}$ does not induce a connected subgraph of poc8_graph: $$\mathrm{poc8\_discb}(S) = \mathrm{true} \implies \neg\, \mathrm{is\_connected\_vertex_set}(\mathrm{poc8\_graph}, \{x \mid S(x) = \mathrm{true}\}).$$
Proof. The Boolean function poc8_discb computes the connected components of the induced subgraph via reachability and tests for nonemptiness. The lemma poc8_discb_sound formalizes the correctness of this decision procedure.
Lemma 4 (poc8_val_eq). For any predicate $P : \mathrm{Fin}\; 8 \to \mathrm{Bool}$, the folded value poc8_val agrees with the real sum over the filtered finset: $$(\mathrm{poc8\_val}(P) : \mathbb{R}) = \sum_{v \in \{x \in \mathrm{Fin}\; 8 \mid P(x) = \mathrm{true}\}} (u(v) : \mathbb{R}).$$
Proof. This is verified by induction on the list of vertices in the universe of $\mathrm{Fin}\; 8$, establishing that the fold over the list coincides with the finset sum.
Lemma 5 (poc8_gmms_check). Every bipartition $P : \mathrm{Fin}\; 8 \to \mathrm{Bool}$ passes the check: $$\forall P : \mathrm{Fin}\; 8 \to \mathrm{Bool},\; \mathrm{poc8\_gmms\_ok}(P) = \mathrm{true}.$$
Proof. There are $2^8 = 256$ possible functions $P : \mathrm{Fin}\; 8 \to \mathrm{Bool}$. In Lean, this check is settled by decision evaluation in poc8_gmms_check.
To see by hand why no connected bipartition can achieve a minimum value greater than 13, let $u = (5, 5, 5, 1, 1, 1, 12, 0)$. The sum of all utilities is: $$5 + 5 + 5 + 1 + 1 + 1 + 12 + 0 = 30.$$ Suppose for contradiction that there exists a bipartition $(T, T^c)$ such that both $T$ and $T^c$ are connected in poc8_graph and $\min(u(T), u(T^c)) \ge 14$. Since the total sum is 30, the pair of values $(u(T), u(T^c))$ must be either $(14, 16)$ or $(15, 15)$.
Vertex 6 has utility 12. Without loss of generality, assume $6 \in T$. Then $u(T \setminus \{6\}) = u(T) - 12 \in \{2, 3, 4\}$. The vertices other than 6 have utilities: - $u(0) = u(1) = u(2) = 5$, - $u(3) = u(4) = u(5) = 1$, - $u(7) = 0$.
Since each of $\{0, 1, 2\}$ has utility 5, none of them can be in $T$. Thus $T \setminus \{6\} \subseteq \{3, 4, 5, 7\}$. The maximum possible sum from $\{3, 4, 5, 7\}$ is $1 + 1 + 1 + 0 = 3$. Therefore:
- $u(T \setminus \{6\})$ cannot be 4, so $u(T)$ cannot be 16.
- Hence $u(T)$ must be either 14 or 15, and $T \setminus \{6\}$ consists of two or three vertices from $\{3, 4, 5\}$, together with 7 if $7 \in T$.
We analyze the location of vertex 7:
Case A: $7 \in T$. Then $7 \notin T^c$, so $T^c \subseteq \{0, 1, 2, 3, 4, 5\}$. Because $\{0, 1, 2\} \cap T = \emptyset$, we have $\{0, 1, 2\} \subseteq T^c$. Furthermore, since $T$ contains at least two vertices of $\{3, 4, 5\}$, $T^c$ contains at most one vertex of $\{3, 4, 5\}$. In poc8_graph, the edges between $\{0, 1, 2\}$ are nonexistent: $\{0, 1, 2\}$ is an independent set. The only possible edges in $T^c$ must go through the single vertex $v \in T^c \cap \{3, 4, 5\}$: - If $v = 3$, the neighbors of 3 are $\{1, 2, 6, 7\}$. Since $0 \notin \{1, 2, 6, 7\}$, vertex 0 has degree 0 in $T^c$. - If $v = 4$, the neighbors of 4 are $\{0, 2, 5, 7\}$. Since $1 \notin \{0, 2, 5, 7\}$, vertex 1 has degree 0 in $T^c$. - If $v = 5$, the neighbors of 5 are $\{0, 1, 4, 7\}$. Since $2 \notin \{0, 1, 4, 7\}$, vertex 2 has degree 0 in $T^c$. - If $T^c \cap \{3, 4, 5\} = \emptyset$, then $T^c = \{0, 1, 2\}$, which has no edges at all. In every subcase, $T^c$ has an isolated vertex and $|T^c| \ge 3$, so $T^c$ is disconnected.
Case B: $7 \notin T$ (so $7 \in T^c$). Then $T \subseteq \{3, 4, 5, 6\}$ with $6 \in T$. The neighbors of 6 in poc8_graph are $\{0, 1, 2, 3, 7\}$. The only neighbor of 6 in $\{3, 4, 5\}$ is vertex 3; 6 is not adjacent to 4 or 5. - If $3 \notin T$, then 6 has no neighbors in $T$, so 6 is an isolated vertex in $T$. Since $|T| \ge 3$, $T$ is disconnected. - If $3 \in T$, then $T$ contains 6, 3, and at least one of $\{4, 5\}$. The neighbors of 4 are $\{0, 2, 5, 7\}$ (not adjacent to 3 or 6). The neighbors of 5 are $\{0, 1, 4, 7\}$ (not adjacent to 3 or 6). Thus, there are no edges in poc8_graph between $\{3, 6\}$ and $\{4, 5\}$. Therefore, any vertex from $\{4, 5\}$ in $T$ cannot be connected to $\{3, 6\}$. Hence $T$ is disconnected.
In every case, either $T$ or $T^c$ is disconnected. Thus, no connected bipartition can achieve a minimum value of 14 or more. Consequently, for every connected bipartition $(T, T^c)$: $$8 \cdot \min(u(T), u(T^c)) \le 8 \times 13 = 104 < 105.$$ This completes the manual verification of Lemma 5.
We now complete the proof of the main theorem.
Proof of poc_linkedness_conjecture_counterexample. We instantiate: - The graph $G$ as poc8_graph. - Linkedness conditions by poc8_linked_two_three and poc8_not_linked_two_four. - The valuation $u$ by casting poc8_u to $\mathbb{R}$, which is nonnegative because all components are natural numbers. - The unconstrained partition witness $S = \{0, 1, 2, 7\}$.
We calculate the values of $S$ and $S^c = \{3, 4, 5, 6\}$: $$u(S) = u(0) + u(1) + u(2) + u(7) = 5 + 5 + 5 + 0 = 15,$$ $$u(S^c) = u(3) + u(4) + u(5) + u(6) = 1 + 1 + 1 + 12 = 15.$$ Thus $\min(u(S), u(S^c)) = 15$, and $7 \cdot \min(u(S), u(S^c)) = 7 \times 15 = 105$. In Lean, this is evaluated on poc8_val and transferred to real sums via poc8_val_eq.
Let $T \subseteq \mathrm{Fin}\; 8$ be any subset such that both $T$ and $T^c$ induce connected subgraphs in poc8_graph (hypotheses $hT$ and $hTc$). We apply poc8_gmms_check to $P = \lambda v, \mathrm{decide}(v \in T)$. The check poc8_gmms_ok yields a three-way disjunction: 1. $8 \cdot \min(\mathrm{poc8\_val}(P), \mathrm{poc8\_val}(\neg P)) < 105$. By poc8_val_eq, $\mathrm{poc8\_val}(P) = \sum_{v \in T} u(v)$ and $\mathrm{poc8\_val}(\neg P) = \sum_{v \in T^c} u(v)$. Casting the inequality to $\mathbb{R}$ gives: $$8 \cdot \min\left(\sum_{v \in T} u(v), \sum_{v \in T^c} u(v)\right) < 105 = 7 \cdot \min\left(\sum_{v \in S} u(v), \sum_{v \in S^c} u(v)\right),$$ which proves the goal. 2. The disconnectedness test returns true on $P$. By poc8_discb_sound, $T$ is not a connected vertex set, contradicting $hT$. 3. The disconnectedness test returns true on $\neg P$. By poc8_discb_sound, $T^c$ is not a connected vertex set, contradicting $hTc$.
In all cases the result follows, concluding the proof of poc_linkedness_conjecture_counterexample.
5. Discussion
The formal verification of poc_linkedness_conjecture_counterexample settles the status of Conjecture 3.10 from arXiv:1908.05433 by showing that it does not hold in general. Specifically, the conjecture fails at $k = 4$.
To understand how this result relates to the general theory, recall that Proposition 3.9 in arXiv:1908.05433 established that whenever a graph $G$ is not $(2, k)$-linked, the price of connectivity is bounded below by: $$\mathrm{PoC}(G, 2) \ge \frac{2k}{2k - 1}.$$ The intuition underlying Conjecture 3.10 was that the positive condition of $(2, k - 1)$-linkedness would simultaneously serve as an upper bound, preventing the gap between unconstrained and connected fair division from widening beyond $2k / (2k - 1)$. This intuition was confirmed for $k = 2$ in Corollary 3.6 of arXiv:1908.05433, where the conjecture holds: if $G$ is $(2, 1)$-linked but not $(2, 2)$-linked, then $\mathrm{PoC}(G, 2) = 4/3$. Furthermore, Theorem 3.11 of arXiv:1908.05433 proved that the conjecture holds for complete graphs minus a nonempty matching.
The 8-vertex graph poc8_graph demonstrates that for $k = 4$, $(2, 3)$-linkedness is insufficient to enforce the upper bound of $8/7$. By concentrating valuation on a high-weight vertex of degree 5 and isolating low-weight independent vertices from high-weight subsets, the graph forces any connected bipartition achieving a balanced split to disconnect one of its sides. As a consequence, the connected maximin share cannot exceed 13, producing a ratio of at least $15/13 \approx 1.1538$, which strictly exceeds $8/7 \approx 1.1429$.
The formal result leaves open several natural questions identified in the context of the problem:
1. Does Conjecture 3.10 hold for $k = 3$? While the case $k = 2$ is true and $k = 4$ is now refuted, the intermediate case $k = 3$ (where the conjecture predicts a price of connectivity of $6/5 = 1.2$) remains open.
2. What is the exact value of $\mathrm{PoC}(G, 2)$ for poc8_graph? The valuation poc8_u proves that the price of connectivity is at least $15/13$. It remains an open question whether $15/13$ is the exact supremum over all additive valuations on this graph, or whether another valuation achieves a strictly larger ratio.
3. Which graph-theoretic structural properties correctly characterize $\mathrm{PoC}(G, 2)$? Given that complete graphs minus a matching satisfy the formula $2k / (2k - 1)$ but general graphs do not, finding the exact graph invariants that govern the price of connectivity in general topologies remains an open problem.
Why it is research-level
- refutes OP-68 (Linkedness and the two-agent price of connectivity)
Lean declarations
- poc_linkedness_conjecture_counterexampleCounterexample to arXiv:1908.05433 Conjecture 3.10 for two agents: there is a graph G on 8 vertices that is (2,3)-linked but not…
- is_connected_vertex_setA vertex set S of a graph G is connected if the subgraph of G induced by S is connected (in particular S is nonempty).
- is_ab_linkedA graph G is (a,b)-linked if for any disjoint vertex sets M1, M2 with |M1| = a and |M2| = b there are disjoint vertex sets S1 ⊇ M1 and S2…
- poc8_graphThe 8-vertex graph G with edges 04, 05, 06, 07, 13, 15, 16, 17, 23, 24, 26, 27, 36, 37, 45, 47, 57, 67.
- poc8_uThe valuation u = (5, 5, 5, 1, 1, 1, 12, 0) on the eight vertices.
- poc8_valThe total u-value of the vertex set selected by P, computed by a fold.
- poc8_gmms_okCheck for a bipartition (P, not P): 8 times the smaller part value is below 105 = 7·15, or one of the two parts is disconnected.
- poc8_linked_two_threeThe 8-vertex graph G is (2,3)-linked: any 2 terminals and 3 further terminals are separated by a connected bipartition of G.
- poc8_not_linked_two_fourG is not (2,4)-linked: for M1 = {0,1} and M2 = {2,5,6,7}, any S1 ⊇ M1 disjoint from S2 ⊇ M2 lies in {0,1,3,4}, and {0,4} is cut off from…
- poc8_gmms_checkEvery bipartition (P, not P) of the eight vertices passes the bipartition check.
- poc8_discb_soundIf the Boolean disconnectedness test accepts S, then S does not induce a connected subgraph of G.
- poc8_val_eqThe folded value agrees with the real sum of u over the selected vertices.
Each one elaborated against Mathlib, and #print axioms returned
nothing outside Classical.choice · Quot.sound · propext.
References
- arXiv:1908.05433 — The Price of Connectivity in Fair Division
Drafted by gemini-3.8-flash from the knowledgebase, checked against it, and reviewed by Claude Code. Only the Lean is verified; the prose is a reading of it.