# Connected subgraphs and their sums

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.)

• Instead of 4,1,1, you could simply use 2,2,2. Also, do you require $a_1,a_2,b_1,b_2$ to be different and $G$ to have at least 4 vertices? – domotorp Sep 29 '19 at 21:28
• It helps me to see why such a constant should exist... By considering $c=0$ we see that your conditions are met: 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] = [0,s]$, regardless of $G$ and $s$. This because we can always find two adjacent vertices $a, b$ such that $\rho(a)+\rho(b)\leq s$, and take $V'= \{a,b\}$. Then by the vertex-disjoint path property $V\backslash V'$ is connected. Perhaps you could add this to the question. – Franka Waaldijk Oct 21 '19 at 9:41
• Another example with $c=5/6$, is to take $K_{3,3}$ with weights of 3,3,3 on one side and 1,1,1 on the other. – Tony Huynh Oct 21 '19 at 15:59
• @nan are you satisfied with the answer below? – mathworker21 Oct 26 '19 at 8:57

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$$.