# Diameters of isomorphic graphs

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?

• It indeed seems likely that isomorphic graphs have the same diameter, for the reason you mention. If you want to be sure, a mathematical proof usually works. Have you tried writing down a proof based on you idea? If so, where did you get stuck? – Discrete lizard Oct 20 at 7:56

## 1 Answer

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$$.