Given an graph $G$ and two, randomly chosen, non-adjacent nodes, let's call them $s$ and $t$, we make the following two notations:

$P_L(s,t;G)$ = the maximum number of internally disjoint paths (paths that don't have any node in common, except s and t) with a length at most $L$ (L ranges from 1 to |G|).

$K_L(s,t;G)$ = the minimum size of a set of nodes (s and t not included in the sets) with this property - if we remove the set of nodes, the result is that there are no more paths of length at most $L$, from $s$ to $t$.

I have to prove the inequality $$ P_L(s,t;G) \le K_L(s,t;G) $$ and specify the values of $L$ (L ranging from 2 to |G|) for which the relation satisfies the equality too, for any chosen graph G and nodes s,t.

The first idea that comes to my mind is to start a discussion based on the values of $L$ and try to prove the relation by induction. Any ideas how?

  • $\begingroup$ Have you started said discussion? $\endgroup$ – Raphael Nov 24 '15 at 15:27
  • 1
    $\begingroup$ Can you edit your question to ask a precise, focused question? This is not a discussion forum, and open-ended calls to discussion are not suitable here. (See our help center.) I'm not sure if that's what you meant by "start a discussion". In any case, can you edit to clarify what your question is? Also, what have you tried? Have you tried proving it by induction, and how far did you get? What approaches did you consider? $\endgroup$ – D.W. Nov 24 '15 at 18:06
  • $\begingroup$ I said that it comes to my mind to debate based on the values of L, not that I have successfully done something. I have no idea how to write this down, where to begin, even if it seems or is simple. That's why I posted this. That's why I need help. If you could give a hint, I would thank you very much. $\endgroup$ – nightwing96 Nov 24 '15 at 19:06
  • 1
    $\begingroup$ What do you mean by "debate based on the values of L"? A mathematical proof is not a debate: it is a logical chain of reasoning. I can't understand what "discussion" or "debate" has to do with this. You have only one sentence with your thoughts, and I can't understand it. We discourage questions that are just a copy-paste of a problem statement without any context or motivation. We want to help you understand, not do your exercise for you. So, what have you tried? What approaches have you considered/tried? What progress have you made so far, and where did you get stuck? $\endgroup$ – D.W. Nov 24 '15 at 20:32
  • 3
    $\begingroup$ Please do not delete your question once it has been answered. $\endgroup$ – Gilles Nov 26 '15 at 11:00

Hint: Suppose that $P_1,\ldots,P_t$ are internally disjoint $(s,t)$-paths of length at most $L$. Show that you have to remove at least one vertex from each path to make the distance from $s$ to $t$ larger than $L$.

When $L = |G|$, the classical Menger's theorem states that equality holds.


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.