Two Paths between Vertices in Cycle Graph

From ProofWiki
Jump to navigation Jump to search

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$

if and only if:

$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

Retrieved from "https://proofwiki.org/w/index.php?title=Two_Paths_between_Vertices_in_Cycle_Graph&oldid=665685"