Diameters of isomorphic graphs

Question

Is it necessary that two isomorphic graphs must have the same diameter? As far as I know, their adjacency matrix must be retained, and if they have the same adjacency matrix representation, does that imply that they should also have the same diameter?

Answer 1

A graph property is an isomorphism-invariant property of graphs. That is, $P$ is a graph property if $P(G_1) \leftrightarrow P(G_2)$ whenever $G_1$ and $G_2$ are isomorphic.

Any property of graphs which doesn't refer to specific names of vertices is a graph property. This includes all the usual properties of graphs: connectivity, diameter (that is, the property of having diameter $D$), chromatic number (that is, the property of having chromatic number $\chi$), and so on. A property of graphs which is not a graph property is: "vertices 1 and 2 are connected".

Let us show that connectivity is a graph property. In the same way, you can show that diameter is one. Let $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ be two isomorphic graphs. This means that there is a bijection $\phi\colon V_1 \to V_2$ such that $(x,y) \in E_1$ iff $(\phi(x),\phi(y)) \in E_2$. We will show that if $G_1$ is connected then $G_2$ is also connected. The same argument (using $\phi^{-1}$) will show the converse, completing the proof.

Suppose that $G_1$ is connected, and let $a,b \in V_2$. Since $G_1$ is connected, there is a path in $G_1$ between $\phi^{-1}(a)$ and $\phi^{-1}(b)$, say $\phi^{-1}(a),v_1,\ldots,v_\ell,\phi^{-1}(b)$. Then $a,\phi(v_1),\ldots,\phi(v_\ell),b$ is a path in $G_2$ connecting $a$ and $b$.