Order and Size of the Cartesian Product of two graphs I want to understand that generally what is the order and size of the Cartesian product $G_{1} \Box G_{2}$ for graphs $G_{1}$ and $G_{2}$.
 A: The Cartesian product of two graphs, denoted as $G_1 \square G_2$, is a graph that has a vertex set consisting of ordered pairs $(v_1, v_2)$, where $v_1$ is a vertex in $G_1$ and $v_2$ is a vertex in $G_2$. The edges in $G_1 \square G_2$ are defined as follows: there is an edge between $(v_1, v_2)$ and $(u_1, u_2)$ in $G_1 \square G_2$ if and only if
(i). either $v_1 = u_1$ and $(v_2, u_2)$ is an edge in $G_2$, or
(ii). $v_2 = u_2$ and $(v_1, u_1)$ is an edge in $G_1$.
It is easy to see that $|V(G\square H)|=|V(G)|\times|V(H)|$. We can see that $|E(G\square H)|= |E(G)| \times |V(H)|+|E(H)|\times |V(G)|$ from the description below.
The Cartesian product of two graphs can be understood in a simpler way:
Step 1:

*

*every vertex of $H$ is replaced by a copy of graph $G$, denoted as $G_1, G_2, \ldots, G_{|V(H)|}$.  (This corresponds to the definition of Cartesian product (ii).)

In this process, we create $|V(H)|$ copies of graph $G$, and thus produce $|E(G)|\times |V(H)|$ edges.
The vertices in  each copy $G_i$ are also labeled consistently with the labeling of vertices in $G$.
Step 2:

*

*select the vertices with the same labeling among $G_1,G_2,\cdots, G_{|V(H)|}$ to reduce $|V(G)|$ copies of $H$. (This corresponds to the definition of Cartesian product (i).)

In this process, we produce $|E(H)|\times |V(G)|$ edges.

