Ajacency matrix proof

38 Views Asked by At

Let $G_1, G_2,G_3$ be 3 graph of order $n$ and size $m$ having ajacency matrices $A_1,A_2,A_3$ respectively.

a) Prove or disprove : $A_1=A_2$ implies $G_1 \cong G_2$

b) prove or disprove: $A_2 \neq A_3$ implies $G_2 \ncong G_3$

for b) I have following counter example

$$A_2 = \left( \begin{array}{ccc} 0 & 1 & 0&1 \\ 1 & 0 & 1&1 \\ 0&1&0&0\\ 1 & 1 & 0&0 \end{array} \right) $$

and

$$A_3 = \left( \begin{array}{ccc} 0 & 0 & 0&1 \\ 0 & 0 & 1&1 \\ 0&1&0&1\\ 1 & 1 & 1&0 \end{array} \right) $$

they are not equal matrices but the graphs are isomorphic.

For a) I know it's true. If $A_1$ and $A_2$ are exactly the same then I can say $V(G_1)=V(G_2)$ and $E(G_1)=E(G_2)$. But if it need to be swapped around then I need to match one vertex to another and I don't know how to explain that.