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