1. 상한graph \(G\)의 radius \(k\), maximum degree \(d = \Delta (G) \)에 대해 다음이 성립한다.\[|G| \le 1 + d \sum _{i=0} ^{k-1} (d-1)^i \] 증명\(z\)를 \(G\)의 central vertex로 놓자.\[D_i := \{v|v\in V \wedge d(v,z) = i\}\]점 집합 \(D_i\)를 \(z\)로부터의 거리가 \(i\)인 점들의 집합으로 놓자. 그러면 다음이 성립한다.\[V(G) = \bigcup _{i=0} ^k D_i \]정의에 의해 \(D_i \cap D_j = \emptyset \)이므로 \(|G| = \sum _{i=0} ^k |D_i|\)이다.여기서 귀납적으로 접근하면\(|D_0| = 1\)(c..

\(G = (V , E) \)가 non-empty graph라고 할 때, 임의의 점 \(v \in V\)에 대해 이웃한 점(neighbours)의 집합을 \(N _G (v) \) 또는 간략하게 \(N(v)\)라고 나타낸다. 이걸 더 일반적으로 확장시켜서, 어떤 점 집합 \(U \subset V \)에 대해 \(N(U)\)는 \(U = \{ u_1 , u_2 , \cdots , u_n \} \)으로 놓았을 때 다음과 같이 정의한다.\[N(U) = \bigcup _{i=1} ^n N(u_i) \setminus U\] 예를 들면 위 그래프에서 \(d(A) = 3\), \(U = \{A,B,C,G\} \)일 때, \(d(U) = 5\)이다. 어떤 점 \(v\)에 대해 \(d(v) = 0\)이면 \(v\)는 '고..