私はグラフに関して少し謎を持っていました。いくつの接続が可能ですか？ （Graph-riddle）
この場合、3つのノードが直接接続されていることは禁じられています。つまり、3つのノード間に3つの接続を作成して三角形を作成することはできません（各コーナーはノードで、エッジは接続です）
2 * nの接続が可能な限り大きいことを証明しますノード。また、この条件が各nに対して実現可能であることを証明する。
nは正の自然数の一部です。
部分的に質問に答えるために、数字n*nが実現可能であることが、nの誘導が使用される次のプルーフスケッチによって解決できることを証明することができます。 n=0の場合、グラフは空です。n=1のグラフは直線です。n=2のグラフは正方形です。誘導ステップについては、ノードのグラフがあり、n*nのエッジを持ち、三角形でないように、nを任意にします。証明の考え方を理解するには、グラフを2つの行、それぞれnノードに配置するとします。このグラフの右側に2つのノードを追加して、n+2=2(n+1)ノードのグラフを作成します。これらのノードを相互に接続し、新しいエッジ1を作成します。
上部の新しいノードを左上の列に接続します。上の行から上の行と下の行を交互に切り替えます。これにより、エッジがnになります。同様に、下側の新しいノードをその左の列に接続します。上の行から上の行と下の行を交互に切り替えます。これにより、エッジがnになります。合計で、構造は三角形を作成しません。
合計で、2*n+1の新しいエッジが作成されました。合計で、グラフは所望の量であるn*n+2*n+1=2*(n+1)の辺を有する。