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.