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
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
댓글
댓글 쓰기