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.


1 Answer 1


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:

                                 / \  
                           2'---2   3---3'  
                                 \ /  

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.