Proof for corollary of non-separable graph

493 Views Asked by At

IF $U$ and $W$ are disjoint sets of vertices in a non-separable graph $G$ of order $4$ or more with $|U|=|W|=2$, then $G$ contain two disjoint paths connecting the vertices of $U$ and vertices of $W$

I tried to prove this corollary.

Let $U =\{u_1, u_2\}$ and $W=\{w_1,w_2\}$. I know that $G$ is non-separable, so every pair of vertices in $G$ must have a common cycle. Every vertex in $U$ have common cycle with every vertex in $W$, so there is a path $u-w$ for every pair of vertex $u,w$. However, I don't know how to show these paths disjoint.

Here is my second attempt

Let $H$ be a graph obtain by adding 2 vertices $a,b$ to $G$, then joining $a$ to $U$ and $b$ to $W$. Since $G$ is non-separable, $H$ is non-separable, thus every 2 vertices of $h$ have common cycle. Therefore, I can find a path $u-w$ that goes through $a,b$.

On the first attempt, I found the path $u-w$ doesn't contain $a,b$, now I found another path $u-w$ that contain $a,b$. So these 2 paths are disjoint.

Does my reasoning sound acceptable?

1

There are 1 best solutions below

0
On

To answer your question, keep in mind to use the following result:

Result: Let $u$ and $w$ be two distinct vertices in a nonseparable graph $G$. If $H$ is obtained from $G$ by adding a vertex $v$ and joining $v$ to $u$ and w, then $H$ is nonseparable.

So, your second attempt is on the right track.

By adding vertex $a$ and joining to vertices of $V(U)$ and similarly adding and joining vertex $b$ to vertices of $V(W)$.

Now, we have obtained a new graph H, that is nonseparable. Vertices $a$ and $b$ are distinct vertices, and must lie on a common cycle.

So, we have the following cycle: $a-u_{1}-***-w_{1}-b-w_{2}-///-u_{2}-a$

Now, by deleting vertices $a$ and $b$ we get $u_{1}-***-w_{1}$ and $w_{2}-///-u_{2}$, two disjoint paths between the vertices of the vertex sets $V(U)$ and $V(W)$ of $G$. $\blacksquare$