1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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$. $\endgroup$ Apr 23, 2021 at 11:32
  • $\begingroup$ All cycles are minimal $2$-connected graphs, but not all minimal $2$-connected graphs are cycles. $\endgroup$ Apr 23, 2021 at 12:46
  • $\begingroup$ 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 ? $\endgroup$ Apr 23, 2021 at 13:59
  • 1
    $\begingroup$ IIRC This is a basic fact of $k-$connected graphs having $k-$ vertex independent paths between u-v. See Menger's theorem. $\endgroup$
    – Calvin Lin
    Apr 23, 2021 at 16:43

0

You must log in to answer this question.