1
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ 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? $\endgroup$ – Discrete lizard Oct 20 at 7:56
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.