If G is self-complementary graph, then 4 \mid |V_{G}| or 4 \mid |V_{G}| - 1

G : undirected simple finite graph, \bar{G} : complementary graph of G.
self-complementary : G \cong \bar{G}

Between complementary graph,
|E_{G}| + |E_{ \bar{G}}| = \frac{|V_{G}|(|V_{G}| - 1)}{2}should be satisfied.

If G \cong \bar{G}, then |E_{G}| = |E_{\bar{G}}|.

Hence, with substitution,
2|E_{G}| = \frac{|V_{G}|(|V_{G}| - 1)}{2} \\[10pt] 4|E_{G}| = |V_{G}|(|V_{G}| - 1) \\[10pt] If |V_{G}| is even integer, then |V_{G}| - 1 is odd integer. Converse is also trivially true.
\therefore 4 \mid |V_{G}| \ \text{or} \ 4 \mid |V_{G}| - 1


댓글

이 블로그의 인기 게시물

Linux에서 특정한 디렉토리가 차지하는 용량을 효율적이고, 빠르게 계산하는 법(Fast, efficient way to calculate directory size recursively on linux)

Proof of well-known 'Intersection Of Three Planes' formula.

'Index type not supported yet' error when doing QR factorization using Eigen and SuiteSparseQR