1
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • $\begingroup$ Have you started said discussion? $\endgroup$
    – Raphael
    Commented Nov 24, 2015 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. ♦
    Commented Nov 24, 2015 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$
    – foxietamine
    Commented Nov 24, 2015 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. ♦
    Commented Nov 24, 2015 at 20:32
  • 3
    $\begingroup$ Please do not delete your question once it has been answered. $\endgroup$
    – Gilles 'SO- stop being evil'
    Commented Nov 26, 2015 at 11:00

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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