# Discrete Math 2-connected graph proof question

Any help would be appreciated, thank you

Proof: Let $$G$$ be a 2-connected graph and $$u$$, $$v$$ be two non-adjacent vertices in $$G$$. Show there must be at least two intern ally-disjoint paths between $$u$$ and $$v$$.

A minimal 2-connected graph is a cycle $$C_{k}$$ where $$k\in \mathbb N$$, $$k≥3$$, then $$\forall u,v\in V(C_{k})$$, we have two distinct paths because $$\forall v\in V(C_{k})$$, $$deg(v)≥2$$. Then, it must be the case that there are at least 2 distinct paths between $$u,v\in V(G)$$ where $$G = (V,E)$$ and $$G$$ is 2-connected. Therefore, claim must hold.

• Since 2-connected graphs are connected there is atleast one path $P$ from $u$ to $v$. Let $x$ be a vertex on the path $P$ which is not equal to $u$ or $v$. Since $G$ is 2-connected, the graph $G \backslash \{x\}$ formed by removing the vertex $x$ is also connected, so there is another path $P'$ from $u$ to $v$ in this graph, which has to be distinct from $P$ since it doesn't visit $x$. Apr 23, 2021 at 11:32
• All cycles are minimal $2$-connected graphs, but not all minimal $2$-connected graphs are cycles. Apr 23, 2021 at 12:46
• yes that is one of the problems there could be in my proof, is there a way I can add that argument as well. How can I do that ? Apr 23, 2021 at 13:59
• IIRC This is a basic fact of $k-$connected graphs having $k-$ vertex independent paths between u-v. See Menger's theorem. Apr 23, 2021 at 16:43