Show that a graph $G$ contains a triangle (1) if and only if there
exist indices $i$ and $j$ such that both the matrices $A_G$ and $A^{2}_{G}$ have the
entry $(i, j)$ nonzero, where $A_{G}$ is the adjacency matrix of $G$ (2).
$1 \implies 2$
If the graph contains a triangle, the entries in the matrix which correspond to edges between the vertices that that make up the triangle will be non-zero.
Each such pair $(i,j)$ will also be non-zero in $A^{2}_{G}$, because there is a path of length two between $i$ and $j$ (within the triangle), starting from $i$, using another vertex $k$
and ending in $j$.
$2 \implies 1$
If $(i,j)$ is 1 in $A_{G}$, then the vertices $i$ and $j$ must be connected. Furthermore, if $(i,j)$ is 1 in $A^{2}_{G}$ that means there must be some other vertex $k$ through which we can go to $j$ starting from $i$.
Hence the edges $(i, j)$, $(i, k)$, $(k, j)$ makes up the triangle.
I had trouble writing down this proof properly. Is the main idea correct?
Best Answer
Let $A_G=\{(a_{ij})\}_{1\le i \le j \le n}$ the adjacent matrix of the graph $G$ and $A^2_G=\{(b_{ij})\}_{1\le i \le j \le n}$. Notice that exists triangle in $G$ if and only if there exists $i,j,k$ such that $a_{ik}\cdot a_{kj}\cdot a_{ij}=1$.
$(\Rightarrow)$ If $a_{ik}\cdot a_{kj}\cdot a_{ij}=1$, we have $a_{ij}=1$ and $b_{ij}=\sum_{l=1}^{n}a_{il}\cdot a_{lj} \neq 0$ (because $a_{ik}\cdot a_{kj}$ is in the sum)
$(\Leftarrow)$ If $b_{ij}=\sum_{l=1}^{n}a_{il}\cdot a_{lj} \neq 0$ and $a_{ij}=1$, there exists $k \in \{1,...,n\}$ such that $a_{ik}\cdot a_{kj}=1$. So, $a_{ik}\cdot a_{kj}\cdot a_{ij}=1$.