Prove that if $G$ and $H$ is Hamiltonian then the Cartesian product $G \times H$ is Hamiltonian
Theorem 3.16: If $G$ is Hamiltonian and $S$ is the vertex cut then
$$k(G-S) \leq |S|$$
This what I got so far
Assume that $G$ of order $n$ and $H$ of order $m$ are Hamiltonian . Let $u \in V(G)$ and $v\in V(H)$.
I know that $G\times H$ has order $nm$ and $deg(u,v)=deg(u) +deg(v) $
But I want to show that $deg(u,v)=deg(u) +deg(v) \geq \frac{nm}{2}$. How can I do that from here? I don't think theorem 3.16 help, because I don't know which kind of graph $G$ and $H$ are.
Heavily revised.
Your statement that $\deg(\langle u,v\rangle)=\deg(u)+\deg(v)$ suggests that the graph product that you have in mind is the Cartesian product, which I’ve seen denoted both by $\times$ and by $\square$: $<\langle u_0,v_0\rangle$ and $\langle u_1,v_1\rangle$ are adjacent in $G\times H$ iff either $u_0=u_1$ and $v_0$ and $v_1$ are adjacent in $H$, or $v_0=v_1$ and $u_0$ and $u_1$ are adjacent in $G$. If that’s the case, it’s not hard to get a Hamilton cycle in $G\times H$ from Hamilton cycles in $G$ and $H$.
Suppose that $G$ has the cycle $u_0,u_1,\ldots,u_m,u_0$, and $H$ has the cycle $v_0,v_1,\ldots,v_n,v_0$. Then we can represent $G\times H$ by an $(m+1)\times(n+1)$ rectangular array of vertices, each row and column of which is a cycle in $G\times H$.
If $n$ is odd, we can get a Hamilton cycle like this:
$$\begin{array}{ccc} v_n&\bullet&\longrightarrow&\bullet&\longrightarrow&\bullet&\longrightarrow&\bullet&\longrightarrow&\ldots&\longrightarrow&\bullet&\longrightarrow&\bullet\\ &\uparrow&&&&&&&&&&&&\downarrow\\ v_{n-1}&\bullet&&\bullet&\longleftarrow&\bullet&\longleftarrow&\bullet&\longleftarrow&\ldots&\longleftarrow&\bullet&\longleftarrow&\bullet\\ &\uparrow&&\downarrow\\ v_{n-2}&\bullet&&\bullet&\longrightarrow&\bullet&\longrightarrow&\bullet&\longrightarrow&\ldots&\longrightarrow&\bullet&\longrightarrow&\bullet\\ &\uparrow&&&&&&&&&&&&\downarrow\\ v_{n-1}&\bullet&&\bullet&\longleftarrow&\bullet&\longleftarrow&\bullet&\longleftarrow&\ldots&\longleftarrow&\bullet&\longleftarrow&\bullet\\ \vdots&\vdots&&\vdots&&\vdots&&\vdots&&&&\vdots&&\vdots&\\ v_1&\bullet&&\bullet&\longrightarrow&\bullet&\longrightarrow&\bullet&\longrightarrow&\ldots&\longrightarrow&\bullet&\longrightarrow&\bullet\\ &\color{blue}\uparrow&&&&&&&&&&&&\downarrow\\ v_0&\bullet&\color{red}\longleftarrow&\bullet&\longleftarrow&\bullet&\longleftarrow&\bullet&\longleftarrow&\ldots&\longleftarrow&\bullet&\longleftarrow&\bullet\\ &u_0&&u_1&&u_2&&u_3&&\ldots&&u_{m-1}&&u_m \end{array}$$
If $n$ is even, we do this instead:
$$\begin{array}{ccc} v_n&\bullet&\longrightarrow&\bullet&\longrightarrow&\bullet&\longrightarrow&\ldots&\longrightarrow&\bullet&\longrightarrow&\bullet\\ &\uparrow&&&&&&&&&&\downarrow\\ v_{n-1}&\bullet&&\bullet&\longleftarrow&\bullet&\longleftarrow&\ldots&\longleftarrow&\bullet&\longleftarrow&\bullet\\ &\uparrow&&\downarrow\\ v_{n-2}&\bullet&&\bullet&\longrightarrow&\bullet&\longrightarrow&\ldots&\longrightarrow&\bullet&\longrightarrow&\bullet\\ &\uparrow&&&&&&&&&&\downarrow\\ v_{n-3}&\bullet&&\bullet&\longleftarrow&\bullet&\longleftarrow&\ldots&\longleftarrow&\bullet&\longleftarrow&\bullet\\ \vdots&\vdots&&\vdots&&\vdots&&&&\vdots&&\vdots&\\ v_1&\bullet&&\bullet&\longleftarrow&\bullet&\longleftarrow&\ldots&\longleftarrow&\bullet&\longleftarrow&\bullet\\ &\color{blue}\uparrow&&\downarrow\\ v_0&\bullet&&\bullet&\longrightarrow&\bullet&\longrightarrow&\ldots&\longrightarrow&\bullet&\longrightarrow&\bullet&\color{red}\longrightarrow\\ &u_0&\color{red}\nwarrow&u_1&&u_2&&\ldots&&u_{m-1}&&u_m&&\color{red}\downarrow\\ &&&\color{red}\longleftarrow&\color{red}\longleftarrow&\color{red}\longleftarrow&\color{red}\longleftarrow&\color{red}\longleftarrow&\color{red}\longleftarrow&\color{red}\longleftarrow&\color{red}\longleftarrow&\color{red}\longleftarrow&\color{red}\longleftarrow \end{array}$$
In each diagram I’ve started at $\langle u_0,v_0\rangle$ and headed up along the blue edge, finishing along the red edge.