Suppose I am given a non-bipartite, undirected graph $G(V,E)$. I create a new graph We $G'(V', E')$ as follows: $V' = V \times V = \{(v_i,v_j) | v_i, v_j \in V\}, E' = \{((v_i,v_j),(v_k,v_l)) | (v_i,v_k),(v_j,v_l) \in E\}$.
Is there any reason why $G'$ is guaranteed to be connected? I guess it has something to do with non-bipartiteness and undirectedness of $G$, but have been thinking about it for hours and am still stuck.
You also need to assume that $G$ is connected. I would use the fact that $G$ is non-bipartite only if it has an odd cycle. Given any two ordered pairs of vertices of $G$, show that you can walk from both pairs along the edges of $G'$ to pairs that have both vertices on the same odd cycle. Can you figure out how to walk from any pair to any pair in an odd cycle?