0
$\begingroup$

My question concerns graph theory.

There is a conjecture I know to be true, but I am not sure whether it has been proven before. It is a fairly simple result. It may be well-known; I am not sure.

Begin Informal Conjecture

I do give a more formal statement of the conjecture later in this post, but first, let us at something which is more intuitive:

Suppose $v$ and $w$ are nodes.
There are paths from $v$ to $w$.
However, there are no really short paths from $v$ to $w$. By this, I mean that is no edge from $v$ to $w$
Every path from $v$ to $w$ contains at least one vertex other than $v$ and $w$
If you must remove $k$ nodes to make there are no more paths from vertex $v$ to vertex $w$, then there is a set of at least $k$ non-overlapping/separate paths from node $v$ to vertex $w$.

Note that when I say that we remove $k$ nodes to break all paths from $v$ to $w$, we are not allowed to remove nodes $v$ and $w$. We have to remove nodes from the graph other than $v$ or $w$.

By "overlapping/separate" paths, I do allow that both paths begin at the same starting node and end at the same final node. However, but the paths never meet, or cross each-other, after leaving their shared origin and before arriving at their mutual destination. The two path interiors have no nodes in common.

End Informal Conjecture

Begin formal definition of $k$-vertex-connected

Let $k \in \mathbb{N}$
Let $D$ be an arbitrary directed graph of at least 2 vertices.
Let $v$ and $w$ be arbitrary vertices in $D$.
Suppose that $V^{\prime}‎$ is an set of $(k-1)$ or fewer vertices in digraph $D$ such that that $v, w \notin V^{\prime}$
Let $D^{\prime}‎$ denote $D^{\prime}‎$ denote the graph formed by $D^{\prime}‎$ by removing the vertices in set $V^{\prime}‎$
$D$ is said to be $k$-vertex-connected if and only if there exists a path from vertex $v$ to vertex $w$ in digraph $D^{\prime}‎$

End formal definition of $k$-vertex-connected

Begin formal definition of $k$-pathy

For any $k \in \mathbb{N}$
For any directed graph $D$
$D$ is $k$-pathy if and only if for every vertices $v$ and $w$ in $D$, if there exists a path in $D$ from $v$ to $w$ and every path from $v$ to $w$ contains at least $2$ edges, then there exists a set of paths $PS$ from $v$ to $w$ such that for every pair of paths $P, Q \in PS$ if $P \neq Q$, then for all vertices $x$ in $D$, if $x$ is in path $P$ and $x$ in path $Q$, then $x \in \{v, w\}$

End formal definition of $k$-pathy

Begin Formal Conjecture

For any $k \in \mathbb{N}$
For any directed graph $D$
$D$ is $k$-pathy if and only if $D$ is $k$-vertex-connected.

End Formal Conjecture

Begin Remark

Being able to say that there are $k$ non-overlapping paths between two nodes is extremely useful in proofs.

It is also very concrete You can draw a picture of $k$ non-overlapping paths very easily.

As an example of a silly application (student-level homework), is if there are at least three paths between two nodes, then there are at least two paths of odd length or two paths of even length. If you glue the two odd paths together or glue the two even paths together, you will get a cycle. The cycle will contain an even number of edges.

Thus, if there exists two nodes in a graph, such that there exists three paths between the two nodes, then there exists an even cycle in the graph.

End Remark

$\endgroup$
2
  • 6
    $\begingroup$ I did not read this but it sounds like en.wikipedia.org/wiki/Menger%27s_theorem $\endgroup$
    – Ville Salo
    Jun 18, 2020 at 21:44
  • $\begingroup$ @VilleSalo You are right. Menger's Theorem says that if there is no directed edge from $x$ to $y$, then minimum number of vertices, distinct from $x$ and $y$, whose removal disconnects $x$ and $y$) is equal to the maximum number of pairwise internally vertex-disjoint paths from $x$ to $y$. $\endgroup$ Jun 19, 2020 at 0:27

1 Answer 1

1
$\begingroup$

This is one of the most fundamental/often used theorems in graph theory. More than 90 years ago, Karl Menger proved the Theorem: Menger's Theorem states that:

if there is no directed edge from $x$ to $y$, then the minimum number of vertices, distinct from $x$ and $y$, whose removal disconnects $x$ and $y$, is equal to the maximum number of pairwise internally vertex-disjoint paths from $x$ to $y$.

$\endgroup$

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