グラフ理論について教えてください。

質問

n,n,n-1,n-1,n-2,n-2,・・・・2,2,1,1(n:正の整数)
というグラフがグラフ的かグラフ的でないかを理由と共に
調べています。

どなたか証明して頂けませんでしょうか？
よろしくお願いいたします。

回答No.3

Tacosan

ちょっと考えたら, もっと簡単に (かつ直接に) 構成できることに気付きました.
結論: 任意の n に対して単純グラフが存在する.
まず, 2n個の頂点 v[1], v[2], ..., v[n-1], v[n], w[1], w[2], ..., w[n-1], w[n] を
v[1], v[n], v[n-1], ..., v[3], v[2], w[2], w[3], ..., w[n-1], w[n], w[1] の順につないだパスを作ります. これで v[1], w[1] の次数は 1, v[2], w[2] の次数は 2です.
あとは, v[k] に対し w[n-(k-3)] から w[n] に辺を引く (対称的に w[k] からも).
これで次数の条件を全て満たすはずです.

回答No.2

Tacosan

つまり, 任意の整数 n に対し「次数が 1, 2, ..., n の頂点が 2個ずつであるような (2n 頂点の) グラフが存在するかどうか」ということでしょうか?
並行辺を持っていいなら, n に関し帰納的に構成することで存在が証明できます.
n = 1 のときは K2, n = 2 のときは 4点からなるパス.
n = 3 のときは 4点からなるサイクルにひげを 2本だす.
以下, 「次数 n の頂点と次数 n-1 の頂点」に隣接する新たな頂点を 2個加え, 次数が 2～n-2 の頂点に対しては適当に辺を加える.
単純グラフに限定すると「以下」のところでうまく選ばないとダメです. 検討してないけど, 適切な選び方は存在しそう.

回答No.1

Tacosan

その数字は何を意味していますか?
「グラフがグラフ的である」とか「グラフがグラフ的でない」とはどういう意味ですか?

補足

この数字はグラフの各点における次数を大きい順に並べた数列です。

『グラフ的である』というのは、上記数列がグラフとして成立するという事です。
また『グラフ的でない』というのは、上記数列がグラフとして成立しないという事です。