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.



댓글

이 블로그의 인기 게시물

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