グラフ理論の頂点に関する性質についての証明

質問

全ての２頂点　v1,v2∈Gについて、ある一つの頂点ｗ∈Gが存在しｖ1とｗは隣接していて、かつ、v2とｗも隣接しているようなグラフGを考える。このとき・・・
（a)ｖ∈Gとｗが非隣接ならばδ(ｖ）＝δ(ｗ）を証明せよ
（b）ある頂点の次数ｋ＞１かつどの頂点にも隣接しているような頂点は一つもない時、すべての頂点の次数はｋになることを証明せよ

の２問について証明の仕方を教えていただけると助かります。問題の状況がそもそもわかりません・・・（δはその頂点から出ている辺の数）
もとの問題が英文なのでそっちも載せておきます。
Let G be a graph. Suppose that for every pair of distinct vertices v1 and v2 in G, there is a unique vertex w in G such that v1 and w are adjacent and v2 and w are adjacent.

(a) Prove that if v and w are nonadjacent vertices in G , then δ(v)＝δ(w).

(b) Prove that if there is a vertex of degree k>1 and no vertex is adjacent to all other vertices, then the degree of every vertex is k.

回答No.2

Tacosan · ベストアンサー

証明しちゃう方が早いかも (苦笑)
v と w は隣接しないとします. このとき, 条件から「v と w の両方に隣接する頂点」は唯一存在します. これを u としましょう.
v に隣接する頂点が u のみであれば, この時点で δ(v) ≦ δ(w) が証明できます. ということで, v に隣接する頂点が u の他にあるとしましょう. それらを x1, x2, ..., xk とします.
さて, 全ての i に対し「xi と w の両方に隣接する頂点」が唯一に存在します. それを yi としましょう.
ここで問題: 「i≠j だが yi = yj」ということはありえるでしょうか?

お礼

証明できました。ありがとうございました＾＾

回答No.1

Tacosan

原文の「unique」を意識して訳すようにしてください.
たぶんこれでいいと思うけど概略だけ:
(a) 「v に隣接する頂点」と「w に隣接する頂点」の間に適切な対応を与えて δ(v) ≦ δ(w) を示す. 「v と w が隣接しないこと」も証明の中で使います.
(b) v, w を隣接しない頂点とすると (a) より δ(v)=δ(w). この v, w に対して「両方に隣接する頂点」を u とすると, u 以外のすべての頂点が「v と w の少なくとも一方とは隣接しない」ことが分かります. そして, その中には u と隣接しない頂点が必ず存在します.

お礼

回答ありがとうございます。
（a)の適切な対応をもう少し教えていただけるとありがたいです。