To work with graph algorithms we need something more precise than a picture. Here comes the **adjacency matrix**! For a graph \(G\) with vertices \(v_1, \ldots, v_n\) we define an \(n \times n\) matrix \(A\) which has \(a_{i,j} = 1 \) when \(v_i\) is connected to \(v_j\) and 0 otherwise.

Has the adjacency matrix: $$ A = \left(\begin{array}{rrrr} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{array}\right) $$

- The diagonals are 0 in adjacency matrices for standard graphs since anything other than 0 would be a loop (pseudo graphs allow them).
- In non-directed graphs \(a_{i,j} = a_{j,i}\), in directed graphs this is not the case. Likewise any symmetric matrix of 0's and 1's can be seen as an adjacency matrix of a pseudograph (graphs require the extra contstraint that the diagonal has a 0 diagonal).
- In the adjacency matrix of a graph (not pseudograph) the sum of the 1s in row \(i\) is the degree of \(v_i\). The same holds for column \(i\).
- The \((i,j)\) entry of \(A^2\) is the number of different walks of length 2 from \(v_i\) to \(v_j\)!
- In general the \((i,j)\) entry of \(A^k\) is the number of walks of length \(k\) from \(v_i\) to \(v_j\).
- Theorem: Two graphs are isomorphic if and only if their vertices can be labeled in such a way that the corresponding adjacency matrices are equal.
- Let \(G_1\) and \(G_2\) be graphs with adjacency matrices \(A_1\) and \(A_2\). \(G_1\) is isomorphic to \(G_2\) if and only if there exists a permutation matrix (an identity with rows shuffled) \(P\) such that \(A_2 = P A_1 P^{T}\).

- What is the adjacency matrix of \(K_n\)? Label the vertices of \(K_{m,n}\) so that the adjacency matrix has an especially nice form.
- If you add all of the values in an adjacency matrix what do you get?
- Let \(A\) be the adjacency matrix of a graph \(G\) with vertices \(v_1, v_2, \ldots, v_n\). Prove that the \(i^{\textrm{th}}\) entry on the diagonal of \(A^3\) equals twice the number of distinct triangles that contain \(v_i\).
- Find the adjacency matrices of these two graphs \(A_1\) and \(A_2\) then find the permutation matrix \(P\) such that \(A_1 = P A_2 P^{T}\) proving them isomporphic.

- The following pseudograph captures all strings made from 'a' and 'b' which only allow one 'b' at a time.

Create an adjacency matrix for it, and try to count all of the strings of length 4, now length \(n\). - Now make a graph for all strings which allow at most two 'b's in a row at a time. Can you answer the same questions?
- What are other ways that a graph could be stored in a computer?