If a graph $G$ with $n \geq 4$ vertices has more than $\frac{3(n-1)}{2}$ edges then there exist $u,v \in V(G)$ with $3$ vertex-disjoint $(u,v)$-paths.

I tried induction but didn't work. Can someone provide me with a hint on how to start?

  • $\begingroup$ Sure got the right type of induction? That one you consider a case for $n=k$ when assuming cases all for $n<k$ already true, so you can delete any vertex you want from the graph, but not add. I'm sure there have to be induction proof if the statement is true. $\endgroup$ Commented May 15, 2020 at 18:02
  • $\begingroup$ @AlexeyBurdin yes, I tried deleting a vertex s.t. the remaing edges would still satisfy the inequality of the induction hypothesis, but I couldn't prove the existence of such vertex. $\endgroup$
    – Andrew
    Commented May 15, 2020 at 18:39
  • 1
    $\begingroup$ I'm mostly just spitballing, but if your condition on the size of the graph implied the existence of an $S_3$ minor (the complement of the net), you'd be done. I seem to recall seeing something similar to this problem in one of Bollobás' books (either extremal graph theory or modern graph theory), and that's the way it was handled. Sorry I'm not of much more help. $\endgroup$ Commented May 19, 2020 at 0:49
  • $\begingroup$ The answer by Hagen von Eitzen is correct. $\endgroup$ Commented May 20, 2020 at 7:22

1 Answer 1


Note that the restriction $n\ge4$ is irrelevant because for $1\le n\le 3$, we have ${n\choose 3}\le\frac {3(n-1)}2$.

Assume $G$ contains a triangle, i.e., vertices $u,v,w$ with edges $uv,vw,wu$. Let $G'$ be $G$ with these three edges removed. Assume there is a path in $G'$ betwen two of the vertices $u,v,w$ and wlog $uz_1\ldots z_mv$ is the shortest such path. Then none of the $z_i$ equals $w$ and so on $G$ we have $uz_1\ldots z_mv$, $uwv$ and $uv$ and are done. Hence $G'$ splits into three disjoint graphs $G_u,G_v,G_w$ with $n_u,n_v,n_w$ vertices and $e_u,e_v,e_w$ edges. We have $$\begin{align}e_u+e_v+e_w&=e-3\\&>\frac{3(n-3)}2\\&=\frac{3(n_u-1)}2+\frac{3(n_v-1)}2+\frac{3(n_w-1)}2\end{align}$$ so that at least one of the $G_x$ has $e_x>\frac{3(n_x-1)}2$ and we are done. We may therefore assume henceforth that $G$ contains no triangle.

Let $uv$ be any edge. Then $u,v $ have no neighbours in common. Hence we obtain a simple graph $G'$ with $n'=n-1$ vertices and $e'=e-1>\frac{3(n-1)}2-1>\frac{3(n'-1)}2$ edges by merging $u$ and $v$ (into $u$). By induction hypothesis, $G'$ has the desired property. Let $xz_1\ldots z_my$, $xz_1'\ldots z_{m'}'y$, $xz_1''\ldots z''_{m''}y$ be three vertex disjoint paths in $G'$. If any of the edges involved is from $u$ to a neighbour of $v$, we can insert $v$ between these points in the path and obtain three paths in $G$. If we have to add $v$ this way at most once, we are done. Hence suppose we have to add $v$ at least twice. Then $u$ occurs twice in the pats and must be an endpoint, wlog. $u=x$. If we need to insert $v$ all three times, we have $vz_1\ldots z_m y$, $vz_1'\ldots z'_{m'} y$, $vz_1''\ldots z''_{m''} y$, and are done. Hence assume we insert $v$ only twice, say in the $z'$ and the $z''$ path. Then we have $vz_1'\ldots z'_{m'} y$, $vz_1''\ldots z''_{m''} y$, $vuz_1\ldots z_m y$, and are done.

  • $\begingroup$ 13 minutes since the answer, still can't read "Hence $G′$ splits into three disjoint graphs" -- how? and "If any of the edges involved is from $u$ to a neighbour of $v$, we can insert $v$ between these points in the path and obtain three paths in $G$", ) $\endgroup$ Commented May 15, 2020 at 20:08
  • $\begingroup$ @AlexeyBurdin The answer is correct. The graph $G'$ splits into connected components. The claim about the insertion of $v$ is correct too, because $v$ is adjacent both to its neighbor and to $u$. $\endgroup$ Commented May 20, 2020 at 7:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .