2013-09-01

■ 答え 17:08

N=奇数の時: さすがに簡単

N=偶数の時:

頂点数6の時の構成をする。簡単にできる。

条件を満たす頂点数2n(N>=3)のグラフをGとすると

Gの頂点全てに向かう頂点Xと

Gの頂点が全て向かう頂点Yをつくり

Y->Xとすると

(X->(G)->Y->Xってかんじです)

X->G G->Yのペアには条件を満たすものがないので

G->Gだけ考えればいいことが分かる。仮定より条件を満たす。

よって頂点数2n+2の条件を満たすグラフG'がつくれることが分かる。

よって示せた。

ツイートする