# Prove that if $G$ and $H$ is Hamiltonian then $G \times H$ is Hamiltonian

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.

• You can't assume that $deg(u) \geq n/2$, since it's only a sufficient condition for Hamiltonicity (it's not necessary). Take the cycle graph $C_n$ for instance. It's Hamiltonian but every vertex is of degree 2. Now, can you specify which product $G \times H$ refers to ? Various people use it for various products... Commented Oct 24, 2014 at 16:34
• A proof that a product of two Hamiltonian graphs is Hamiltonian also is here. Commented Oct 27, 2016 at 4:05

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.

• Can you explain a little bit further please? I still can't see how this make the Cartesian product $G \times H$ Hamiltonian, since I still don't know what are $G$ and $H$. Commented Oct 25, 2014 at 2:52
• @Diane: I really didn’t explain that very well before, so I’ve completely revised and expanded the answer. Commented Oct 25, 2014 at 4:07
• for part $n$ is even, a between $v_{n-3}$ and $v_1$, you go to the right for any even subscript of $v$ and go to the left for odd subscript? Commented Oct 25, 2014 at 14:22
• @Diane: Yes. Once you go up to the top, you just snake back and forth until you reach the bottom. Commented Oct 25, 2014 at 18:40

If you consider the cartesian product of a cycle and a path $$G=C_m\square P_n$$, it is not too hard to show that:

• If $$n=1$$, $$G$$ is hamiltonian.
• If $$m$$ or $$n$$ are even, it is hamiltonian because in that case it is a subgraph isomorphic to the product of paths $$P_n\square P_m$$ (which is hamiltonian) (you have to prove it by the way, but inspecting the graph and considering cases you'll be able to do it).
• If both $$m$$ and $$n$$ are odd, you can construct a cycle in the fashion of the other answer.

Then, if $$H$$ and $$K$$ are hamiltonian graph, $$H\square K$$ is hamiltonian since both have as a subgraph a cycle (in particular a hamiltonian one), and one of the cycles have a path as a subgraph. Then use what we stated before.