無向問題について

隣接行列

A=(0 1 1 0 が与えられた時
1 0 1 1
1 1 0 0
0 1 0 0)(A)ij,(A^2)ijのどちらも０でないようなi,jが存在する時グラフに含まれる三角形が少なくともⅠつは存在するということを示したいのですがどうすれば良いでしょうか

No.1 回答者： stomachman 回答日時： 2017/07/14 11:54

Aij=1というのは、iとjが直接繋がってるということ。

(A^2)ij=1というのは、あるnode kがあって、iからkを介してjにつながってるということ。
k≠iかつk≠jの場合（つまりAの対角成分に1がない場合）に限れば、３つのnode i,j,kは、iとk, kとj, jとiが直接繋がってるということだ。