There are 2 non empty sets $A$ and $B$, such that $A \cap B = \emptyset $. And there is a function $f: A \rightarrow B$ which defines the undirected graph $G=(V,E)$ such that $V=A \cup B$ and $E= A \times A \cup \{(x,f(x)) | x\in A\}$.
How can I prove that Graph $G$ is connected if and only if $f$ is surjective. Does anyone knows how to prove this.
On
f surjective. For x,y in A, (a,a) is an arc. z in B, z=f(u), (u,f(u)) an arc thus for every x in A there is a path x to u and u to z. v and v' in B v=f(w) v'=f(w') w, w' in A, you have an arc from v to w , w to w' and w' to v'
f not surjective z not in the image of A, you can't have a path from x to z, x in A since an arc contains z if and only if it is of the form (u,f(u)=z)
We know that all elements of $A$ are connected to each other because $A\times A$ is part of the edge set.
If $f$ is surjective then for any $b\in B$ there exists $a\in A$ such that $f(a)=b$ so there is an edge from $a$ to $b$. If $b'$ is another element of $B$, there is another $a'\in A$ such that $f(a')=b'$ so $a'$is connected to $b'$. Therefore, by transitivity of the connections in a graph, all elements of $A$ and $B$ are connected.
Conversely, if the graph is connected, let $b\in B$ be chosen arbitrarily. By the definition of the edge set there are no elements of $B$ directly connected to $b$. Therefore, if we take any vertex a distance of $1$ away from $B$ it must be in $A$, call it $a$. Then $f(a)=b$ and therefore, $f$ is surjective.