Connected subgraphs and their sums

Question

Let $G=(V,E)$ be an undirected graph with $|V|\geq 4$ such that for any distinct vertices $a_1,a_2,b_1,b_2$, there is a path from $a_1$ to $a_2$ and a (vertex-)disjoint path from $b_1$ to $b_2$ (in other words, the graph is $2$-linked).

Assign a nonnegative real number to each vertex in $V$. Suppose the sum of these numbers is $2s$, and a subset of them has sum exactly $s$. What is the largest constant $c$ for which (regardless of $G$ and $s$) there always exists a subset $V'\subseteq V$ such that both $V'$ and $V\backslash V'$ form connected subgraphs, and the sum of the numbers in $V'$ belongs to $[cs,s]$?

The following example shows that $c\leq 5/6$: a clique $K_5$ with one edge $e$ removed, numbers $3,3$ on the two vertices adjacent to $e$, and $2,2,2$ on the remaining vertices. Another example is to take $K_{3,3}$ with $3,3,3$ on one side and $1,1,1$ on the other. Is $c=5/6$ tight?

(It is easy to see that such a constant $c$ must exist: $c=0$ works since for any connected graph, its vertices can be partitioned into two parts such that both parts are connected.)

Answer 1

Here is an argument that shows a lowerbound of $c \geq \frac{2}{3}$. For this, we only need the weaker assumptions that $G$ is $2$-connected and the weight of each vertex is at most $\frac{W}{2}$, where $W$ is the total weight. Both these assumptions are clearly implied by the hypotheses of the original question.

Theorem. Let $G=(V,E)$ be a $2$-connected graph and $w: V \to \mathbb{R}_{\geq 0}$ be such that $w(v) \leq \frac{1}{2}\sum_{u \in V} w(u):=\frac{W}{2}$ for all $v \in V$. Then there exists a subset $X \subseteq V$ such that $G[X]$ and $G[V \setminus X]$ are both connected and $\frac{W}{3} \leq \sum_{u \in X} w(u) \leq \frac{W}{2}$.

Proof. We proceed by induction on $|E|$. If $|E|=3$, then $G=K_3$. In this case, there is a vertex $x$ with $w(x) \geq \frac{W}{3}$, so we may take $X=\{x\}$. For the inductive step, first note that we may assume $w(u) < \frac{W}{3}$ for all $u \in V$. Otherwise, we can take $X=\{u\}$, since $G-u$ is connected by $2$-connectivity. Choose a spanning tree $T$ of $G$, and let $x$ be a leaf of $T$ and $y$ be the unique neighbour of $x$ in $T$. By assumption, $w(x)+w(y) < \frac{2W}{3}$. If $w(x)+w(y) > \frac{W}{2}$, we may take $X=V \setminus \{x,y\}$. Therefore, we may assume that $w(x)+w(y) \leq \frac{W}{2}$. We use the well-known fact that in a $2$-connected graph, every edge can be either deleted or contracted to maintain $2$-connectivity. Let $e=xy$. If $G \setminus e$ is $2$-connected, we can apply induction. If $G / e$ is $2$-connected, we let the contracted vertex have weight $w(x)+w(y)$ and we apply induction. $\square$

Note that $2$-connectedness is required to prove $c>0$. To see this consider a star with $k$ leaves where each leaf has weight $1$ and the center of the star has weight $k$.