a doubt in finding distance in graph theory I was studying about a product graph which is defined as : !enter image description here. **I am taking $G_1$ and $G_2$ as connected graphs.** I found that for any 2 vertices $(g,h),(g',g')$, $d(g,h),(g',h')$ = 1 if $g \sim g'$ or $h\sim h'$ $d(g,h),(g',h')$ = 2 if $ g=g' ~or ~h=h'$ $d(g,h),(g',h')$ = min{d(g,g'),d(h,h')}, otherwise. Here d denotes the distance between vertices and ~ means adjacency. Am I right in finding the above result? Is there any flaw. Please rectify if I am wrong. Heartily thanks. **_NOTE_** : 1st clause in the the formula directly follows from definition. In 2nd clause i took g=g'. the the vertices are like (g,h) and (g,h'). There must exist a vertex _b_ such that _g_ is adjacent to _b_. thus we get a path of length 2: (g,h)(b,c)(g,h'), where c is any vertex in $G_2$. thus distance is 2 in this case. I am doubtful about 3rd clause.

We do not need to assume $G_1,G_2$ connected. It is sufficient to assume that $G_1,G_2$ have no isolated vertices. Then for $(g,h),(g',h')\in V(G)$ pick $a\in G_1$ with $g\sim a$ and $b\in G_2$ with $h'\sim b$. Then $(g,h)\sim (a,b)\sim (g',h')$ shows that all distances in $G$ are $\le 2$ (and especially that $G$ is connected.