TU Wien:Diskrete Mathematik für Informatik UE (Gittenberger)/Übungen WS13/Beispiel 4

4) Use the adjacency matrix of the following graph G₁ in order to compute the number of triangles (i.e. cycles of length 3) of G₁!

Theory

• Adjacency matrix
• Paths in adjacency matrices (german) $A_{i,j}^{k}$ gives the number of paths of length $k$ between the vertices $v_{i},v_{j}$
• Matrix multiplication
• Permutation

Solution

$A={\begin{pmatrix}0&1&1&1\\1&0&1&1\\1&1&0&1\\1&1&1&0\end{pmatrix}}A^{2}={\begin{pmatrix}3&2&2&2\\2&3&2&2\\2&2&3&2\\2&2&2&3\end{pmatrix}}A^{3}={\begin{pmatrix}6&7&7&7\\7&6&7&7\\7&7&6&7\\7&7&7&6\end{pmatrix}}$

Cycles are on the diagonal in the power of the adjacency matrix. We therefore have $6+6+6+6=24$ cycles of length 3. Note that not all of them are unique! We have to avoid vertex permutations (e.g $1-2-3-1$ is the same triangle as $1-3-2-1$ and $1-2-3-1$ is the same triangle as $2-3-1-2$). The number of permutations is 6. The number of triangles is therefore $24/6=4$

• $1-2-3-1$
• $1-2-4-1$
• $1-3-4-1$
• $2-3-4-2$