$[$This main motivation for this problem is to see that if the graph is given to you in a matrix form, you may

be able to use matrix operations to answer certain questions.$]$

A triangle in an undirected, simple graph is a set of three distinct vertices x$,$ y$,$ z such that all pairs are

connected by an edge.

$1.$ Consider the following algorithm that takes as input an adjacency matrix of a simple undirected graph

G and returns True if there exists a triangle and returns False if there is not a triangle

Consider the following algorithm that takes as input an adjacency matrix of a simple undirected graph

$G$ and returns True if there exists a triangle and returns False if there is not a triangle.

Triangle $1(G)(G,$ an undirected simple graph with $n$ vertices in adjacency matrix form.$)$

for $i=1,$dots,$n$ :

for $j=1,$dots,$n$ :

if $G[i,j]==1$ :

$,$ for $k=1,$dots,$n$ :

$,$ if $G[i,k]==1$ and $G[j,k]==1$ :

return True

return False

$(3$ points$)$ Show that the runtime for this algorithm is $O(|V{|}^2+|V||E|).$

$(3$ points$)$ In order for Triangle$1$ to return True, what needs to happen and why does this correspond

to a triangle?

Consider the following algorithm that takes as input an adjacency matrix of a simple undirected graph

$G$ and returns True if there exists a triangle and returns False if there is not a triangle.

Triangle$2(G)(G,$ an undirected simple graph with $n$ vertices in adjacency matrix form.$)$

Compute $H=GG.$

for $i=1,$dots,$n$ :

for $j=1,$dots,$n$ :

$,$ if $G[i,j]==1$ AND $H[i,j]>0$ :

return True

return False

$(3$ points$)$ Assuming that matrix multiplication between two $nn$ matrices takes $O(n^{2\mathrm{.}81})$ time,

calculate the runtime of this algorithm.

$(3$ points$)$ In order for Triangle $2$ to return True, what needs to happen and why does this correspond

to a triangle? $($In particular, what does it mean for $H[i,j]=1$ or $H[i,j]=2?)$

$(3$ points$)$ Is Triangle$1$ or Triangle$2$ more efficient? $($Justify your answer.$)($Hint: think about dense

and sparse graphs.$)$