The only self-complementary cycle graph is $C_{5}$
$G$ : undirected simple finite graph, $\bar{G}$ : complementary graph of $G$.
$C_{n} (n \geq 3)$ : n-cycle graph, which is the graph itself is a cycle.
To be $G$ self-complementary, $G \cong \bar{G}$ should be satisfied. Hence, $G$ and $\bar{G}$ must have same number of edges. Which implies that $|E_{G}| = |E_{ \bar{G}}| = \frac{1} {2} \cdot \frac{|V_{G}|(|V_{G}| - 1)}{2}$ (Note that $|V_{G}| = |V_{\bar{G}}|$ by definition of complementary graph).
From the fact that $C_{n}$ is cycle graph, $|E_{C_{n}}| = |V_{C_{n}}| = n$ and $|E_{C_{n}}| = |E_{\bar{C_{n}}}|$,
$$
|E_{C_{n}}| + |E_{\bar{C_{n}}}| = \frac{|E_{C_{n}}|(|E_{C_{n}}| - 1)}{2} \\[10pt]
2n = n(n-1) \\[10pt]
n(n - 5) = 0 \\[10pt]
\therefore n = 0, 5$$
Since that $n \geq 3$, the only answer is $5$.
$C_{n} (n \geq 3)$ : n-cycle graph, which is the graph itself is a cycle.
To be $G$ self-complementary, $G \cong \bar{G}$ should be satisfied. Hence, $G$ and $\bar{G}$ must have same number of edges. Which implies that $|E_{G}| = |E_{ \bar{G}}| = \frac{1} {2} \cdot \frac{|V_{G}|(|V_{G}| - 1)}{2}$ (Note that $|V_{G}| = |V_{\bar{G}}|$ by definition of complementary graph).
From the fact that $C_{n}$ is cycle graph, $|E_{C_{n}}| = |V_{C_{n}}| = n$ and $|E_{C_{n}}| = |E_{\bar{C_{n}}}|$,
$$
|E_{C_{n}}| + |E_{\bar{C_{n}}}| = \frac{|E_{C_{n}}|(|E_{C_{n}}| - 1)}{2} \\[10pt]
2n = n(n-1) \\[10pt]
n(n - 5) = 0 \\[10pt]
\therefore n = 0, 5$$
Since that $n \geq 3$, the only answer is $5$.
댓글
댓글 쓰기