Two Paths between Vertices in Cycle Graph
Theorem
Let $G$ be a simple graph.
Let $u, v$ be vertices in $G$ such that $u \ne v$.
Then:
- for any two vertices $u, v$ in $G$ such that $u \ne v$ there exists exactly two paths between $u$ and $v$
- $G$ is a cycle graph.
Proof
Necessary Condition
This theorem requires a proof. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by crafting such a proof. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{ProofWanted}} from the code.If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page. |
Sufficient Condition
Let $G = \struct {V, E} = C_n$ be the cycle graph of order $n$.
Let $V = \set {v_1, v_2, \ldots, v_n}$
Let $u, v \in C_n$.
Then both $u, v$ are on the cycle $C = \tuple {u, u_1, u_2, \ldots, u_p, v, v_1, v_2, \ldots, v_q, u}$ where $p + q + 2 = n$.
By definition of cycle graph this is the only cycle in $G$.
Let $e$ be the edge $u u_1$ of $G$ (or, if $u$ and $v$ are adjacent, let $e = u v$).
From Size of Cycle Graph equals Order, there are exactly $n$ edges in $G$.
Then the edge deletion $G \setminus e$ has $n - 1$ edges.
By Finite Connected Simple Graph is Tree iff Size is One Less than Order it follows that $G \setminus e$ is a tree.
Thus by Path in Tree is Unique there is exactly $1$ path from $u$ to $v$ in $G - e$, that is:
- $P_1 = \tuple {u, v_q, v_{q - 1}, \ldots, v_2, v_1, v}$
By replacing $e$, there exist a second path from $u$ to $v$ in $G$:
- $P_2 = \tuple {u, u_1, u_2, \ldots, u_{p - 1}, u_p, v}$
or if $u$ and $v$ are adjacent:
- $P_2 = \tuple {u, v}$
$\blacksquare$
Sources
- 1977: Gary Chartrand: Introductory Graph Theory ... (previous) ... (next): $\S 4.1$: The Minimal Connector Problem: An Introduction to Trees: Problem $5$