$G \times H$ regular $\implies G $ and $H$ regular?

79 Views Asked by At

I know that if two graphs $G,H$ are regular then their Cartesian product is also regular. But I never heard of the veracity of the converse. Is is true ? I think yes by the following argument but I am not sure :

We can show the contrapositive : If $G$ or $H$ is not regular then (wlog) we can assume $G$ is not regular then there exists two vertices $g_1,g_2 \in V(G)$ such that $n=\deg(g_1)\neq \deg(g_2) =m$. Then let $h \in H$, we have in $G \times H$ : $$\deg (g_1,v)=n+\deg(v)\neq\deg (g_2,v)=m+\deg(v)$$

So $G \times H$ is not regular. Is it correct ? I also noticed that if we assume a property on $G$ and $H$ then $G \times H$ also verifies it (for example $G,H$ bipartite $\iff G \times H$ bipartite), is there a counterexample for that ?

1

There are 1 best solutions below

0
On BEST ANSWER

Your argument is correct (except you switched from $h$ to $v$).

A counterexample is given by planarity – for instance, the hypercube graph $Q_n$ is planar exactly if $n\le3$, so planarity is not inherited in $Q_4\cong Q_1\times Q_3\cong Q_2\times Q_2$.