How to show that there is at least one triangle in G

Question

Let $G$ be a undirected graph and $A$ be a its adjacency graph. How should I proof that there is at least one triangle in $G$ if there exist $i,j$ such that neither $(A)_{ij}$ nor $(A^2)_{ij}$ is $0$? Sorry but I have no idea to show this. Can someone help me to show this? Thank you in advance.

Answer 1

The adjacency matrix $A$ of a graph $G$ tells us if two vertices are connected when $A_{ij} = 1$.

The component $A^n_{ij}$ of the $n$-th power of the adjacency matrix tells us the number of paths between $i$ and $j$ which are of length $n$.

Hence, in this case $A_{ij} \neq 0$ implies $i$ and $j$ are connected and $A_{ij}^2 \neq 0$ implies there exists a path of length 2 that connects $i$ and $j$.

Therefore, the union of this path and the edge $ij$ gives us a triangle.