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