# To prove that the graph with a bijection function is connected

There is graph $(V,E)$, given that it is finite, connected undirected graph.

$W$ is a finite set and $f:V \rightarrow W$ is a bijective function.

I need to prove $(V \cup W,E \cup \{ (v, f(v))| v \in V \})$ is connected.

Can anyone tell what will be the set of edges here and how will bijection help in the connectivity.

Let $G=\langle V,E\rangle$ be the original graph, and let $G'$ be the new graph. $G'$ has all of the edges that $G$ had. In addition, for each vertex $v\in V$ it has an edge between $v$ and $f(v)$. For example, if $G$ is a $4$-cycle, $G'$ looks like this:

                                  1'
|
1
/ \
2'---2   3---3'
\ /
4
|
4'


Here $V=\{1,2,3,4\}$, $W=\{1',2',3',4'\}$, and for each $v\in V$, $f(v)=v'$.

• Thank you Brian!, you made it so clear. Nov 4, 2015 at 18:34
• @TechJ: You’re welcome! Nov 4, 2015 at 18:34