Adding edges in two graphs with same connectivity, the connectivity is still maintained?

46 Views Asked by At

Let $G$ be a graph. Denote $G[A] = (V(G),A)$. We say that two vertices $x$ and $y$ are connected in $G$, if there exists a path from $x$ to $y$ in $G$.

Let $I \subseteq E(G)$ and $I' \subseteq E(G)$ (edges arbitraries). Let $J \subseteq E(G)$ such that $I \cap J = \emptyset$.

I know that two vertices $x$ and $y$ are connected in $G[I]$ if and only if $x$ and $y$ are connected in $G[I']$.

If two vertices $u$ and $v$ are not connected in $G[I \cup J]$, then $u$ and $v$ are not connected in $G[I' \cup J]$? Does this follow from the previous affirmation?

Another thing: is this true only if $I \cap J = \emptyset$ or else is this still valid?

1

There are 1 best solutions below

0
On

This seems to be true, whether $I\cap J=\emptyset$ or not.

Let's show that if $u$ and $v$ are connected in $G[I'\cup J]$ then $u$ and $v$ are connected in $G[I\cup J]$. If $u$ and $v$ are connected in $G[I'\cup J]$, then there is a path $u=x_{0},x_{1},...,x_{n-1},x_{n}=v$ in $G[I'\cup J]$. This means that every $\left\{x_{i},x_{i+1}\right\}$ is either in $J$ or in $I'$. In the former case, it is also an edge in $G[I\cup J]$. In the latter case, $x_{i}$ and $x_{i+1}$ are connected in $I'$, so there is also a path $x_{i}=x_{i\ 1},x_{i\ 2},...,x_{i\ k_{i}}=x_{i+1}$ in $I$ hence in $I\cup J$.

Altogether, this implies the existence of a path $u=x_{0},x_{0\ 2},...,x_{0\ k_{0}}=x_{1}=x_{1\ 1},x_{1\ 2},...,x_{1\ k_{1}}=x_{2},...x_{n-1},x_{n-1\ 2},..,x_{n-1\ k_{n-1}}=x_{n}$ in $G[I\cup J]$.