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$ – Alexey Burdin May 15 '20 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 May 15 '20 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$ – Paralyzed_by_Time May 19 '20 at 0:49
  • $\begingroup$ The answer by Hagen von Eitzen is correct. $\endgroup$ – Alex Ravsky May 20 '20 at 7:22

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$ – Alexey Burdin May 15 '20 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$ – Alex Ravsky May 20 '20 at 7:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.