How demonstre that a graph is connected? I was wondering if someone can help me understand how to prove this theorem .
We consider the following binary operation $\otimes$ on graphs: if $G_i = (V_i,E_i) (i = 1,2)$ are two graphs, then $G_1 \otimes G_2$ is the following graph: $V (G_1 \otimes G_2) = V_1 \times V_2$ and $E(G_1 \otimes G_2) = \{(u_1,u_2)(v_1,v_2) : u_1v_1 \in E_1,u_2v_2 \in  E_2\}$.
Prove that $G_1 \otimes G_2$ is connected if and only if $G_1$ and $G_2$ are connected and one of them contains an odd circuit.
 A: The notation provided by Henno's edit suggests this product in particular is the tensor (or Kronecker) product for graphs.
It is named so, as it comes up when considering the graph whose adjacency matrix is the Kronecker product of two other adjacency matrices. To be precise, if $A_1$ and $A_2$ are the adjacency matrices of graphs $G_1$ and $G_2$ then $G_1 \otimes G_2$ is defined to be the graph whose adjacency matrix is $A_1 \otimes A_2$. This is equivalent to your definition. We follow Weichsel's paper on this topic. I will attempt to provide commentary elaborating on the details of the proofs.

First it is useful to determine when walks in $G_1$ and $G_2$ give rise to a walk in the $G_1 \otimes G_2$. To this end, the lemma due to Weichsel is helpful.
Lemma 1. If $p_0 q_1$ and $p_n q_m$ are vertices of $G \otimes H$ and if there exist $p_0 \to p_m$ in $G$ and $q_0 \to q_,$ in $H$ such that $\ell(p_0 \to p_m) + \ell(q_1 \to q_2)$ is even then there exists $p_0q_0 \to p_n q_m$ in $G \otimes H$.
The notation $p_1 \to p_2$ denotes a walk starting at vertex $p_1$ and ending at $p_2$, and $\ell(p_1 \to p_2)$ denotes the length of the walk. We also write $\ell$ instead of writing $n$ to denote length as the paper does.
The idea of the proof is to consider two walks side-by-side and simultaneously step forward in each walk in order to obtain a walk in $G \otimes H$. If the walks are the same length then $n = m$ so we take the walk $(p_0 q_0, p_1 q_1, \ldots, p_n q_n)$ in $G \otimes H$. If the walks differ in length, then the idea is the same up until we reach the end of one of the walks. Suppose $n < m$. We constructed the walk $(p_0 q_0, p_1 q_1, \ldots, p_n q_n)$ in $ G \otimes H$ and must extend it to reach $p_n q_m$. Thus, we consider a vertex $p$ adjacent to $p_n$ and take the walk $(p_n q_n, p q_{n+1}, p_n q_{n+2}, \ldots, p q_{m-1}, p_n q_m)$. Note that in order for this to actually end at $p_n q_m$ and not at $p q_m$ the sums of the two walk lengths is required to be even (see why this is true). Joining the two walks gives us $p_0 q_0 \to p_n q_m$.
Theorem 1 of Weichsel's paper gives the solution to your question. Note that your question involves the connectivity of $G$ and of $H$, but it is easy to prove that if $G \otimes H$ is connected then both $G$ and $H$ are connected.
Theorem 1. Let $G$ and $H$ be connected graphs. $G \otimes H$ is connected if and only if either $G$ or $H$ contains an odd cycle.
Proof. 
The easy direction is $(\impliedby)$. Let $p_0 q_0$ and $p_n q_m$ be two vertices of $G \otimes H$, and let $p_0 \to p_n$ and $q_0 \to q_m$ be walks in $G$ and $H$, respectively. We consider the parity of $\ell(p_0 \to p_n) + \ell(q_0 \to q_m)$ in order to apply the above lemma. Certainly if the sum is even, the lemma guarantees a walk connecting the above two arbitrary vertices, meaning $G \otimes H$ is connected. Otherwise, the sum is odd. We attempt to make use of the above lemma by extending one of the two walks in such a way that the sum of their lengths would be even. To this end, suppose $G$ contains an odd cycle and let $p$ be the terminal vertex of that cycle. Since $G$ is connected there is a walk $ p_0 \to p $ of unknown length. There is also an odd circuit $p \to p$ that takes the vertices of the cycle. We take the reverse of $p_0 \to p$ to get back to $p_0$ from the cycle. Since $p \to p_0$ is the reverse, it has the same length. Composing these three walks, we have a closed walk $p_0 \to p_0$ of length
\begin{align}
\ell(p_0 \to p_0) &= \ell(p_0 \to p) + \ell(p \to p) + \ell(p \to p_0)\\
&= 2 \ell(p_0 \to p) + \ell(p \to p).
\end{align}
Since $\ell(p \to p)$ is odd, the composed closed walk $p_0 \to p_0$ is of odd length. Now $\ell(p_0 \to p_0, p_0 \to p_n) + \ell(q_0 \to q_m)$, ("," denotes walk composition) is even since the original sum was odd. Thus by the lemma we have a walk $p_0 q_0 \to p_n q_m$ in $G \otimes H$.
$(\implies)$
Conversely, let $p_0$ and $q_0, q_m$ be vertices in $G$ and $H$, respectively, such that $q_0$ is adjacent to $q_m$ in $H$. Then $p_0 q_0$ and $p_0 q_m$ are vertices in $G \otimes H$, hence must be connected by our assumption. Denote this walk by $(p_0 q_0, p_1 q_1, \ldots, p_{m-1} q_{m-1} p_0 q_m)$. Here is where it gets a little tricky. For each vertex in the above walk, we consider the distance to the end vertex in each component $G$ and $H$. That is, for $p_i q_i $ in the walk we consider $d_G(p_i, p_0)$ and $d_H(q_i, q_m)$. As we go through the vertices in the walk, notice that these distances can differ by at most $1$, hence $ |d_G(p_i, p_0) - d_G(p_{i+1}, p_0)| \leq 1$. This is because each component vertex must be adjacent to the next in $G$ and $H$. We make the following claim.
Claim 1. There exist two adjacent vertices $p_i q_i$ and $p_{i+1} q_{i+1}$ in the walk such that $d_G(p_i, p_0) = d_G(p_{i+1}, p_0)$ or $d_H(q_i, q_m) = d_H(q_{i+1}, q_m)$.
To see this, we consider the sum $s_i = d_G(p_i, p_0) + d_H(q_i, q_m)$ and investigate how its parity changes from vertex-to-vertex in the walk. If $|d_G(p_i, p_0) - d_G(p_{i+1}, p_0)| = 0$ or $|d_H(q_i, q_m) = d_G(q_{i+1}, q_m)| = 0$ for some $i$, then we are done. Suppose then that this is not true for any $i$. Then $|d_G(p_i, p_0) - d_G(p_{i+1}, p_0)| = 1$ or $|d_H(q_i, q_m) = d_G(q_{i+1}, q_m)| = 1$ for all $i$, which implies $s_i \equiv s_{i+1} \mod 2$ for all $i$. Considering the start and end vertices of the walk, we see that $d_G(p_0, p_0) = 0$, $d_H(q_0, q_m) = 1$ (recall that they are adjacent), and $d_G(p_{m-1}, p_0) = 1$, $d_H(q_{m-1}, q_m) = 1$. Then $s_0 = 1$ while $s_{m-1} = 2$, which is a contradiction since the sum must not change parity in this case. 
Now that we have two vertices $p_i q_i$ and $p_{i+1} q_{i+1}$ satisfying the above claim, suppose $d_H(q_i, q_m) = d_H(q_{i+1}, q_m)$. Then there are two paths $q_i \to q_m$ and $q_{i+1} \to q_m$ in $H$ both of the same length. Since they end at the same vertex, they must eventually meet, so let $q$ be such a meeting vertex. It follows that $\ell(q_i \to q) = \ell(q_{i+1} \to q)$ otherwise one of the paths would be longer than the other, contradicting their distances being the same. Thus we have a circuit $q_i \to q, q \to q_{i+1}, q_{i+1} \to q_i$. To see that it is odd, we perform a similar calculation:
\begin{align}
\ell(q_i \to q, q \to q_{i+1}, q_{i+1} \to q_i) &= \ell(q_i \to q) + \ell(q \to q_{i+1}) +  \ell(q_{i+1} \to q_i)\\
&= 2 \ell(q_i \to q) + \ell(q_{i+1} \to q_i)\\
&= 2 \ell(q_i \to q) + 1 \text{          (since $q_i$ is adjacent to $q_{i+1}$)}.
\end{align}
Therefore, we have shown there is an odd circuit in $H$. A similar argument works for $G$.
