A graph is self-complementary if it is isomorphic to its complement. For all self-complementary graphs on n vertices, n is
A
A multiple of 4
No worries! We‘ve got your back. Try BYJU‘S free classes today!
B
Even
No worries! We‘ve got your back. Try BYJU‘S free classes today!
C
Odd
No worries! We‘ve got your back. Try BYJU‘S free classes today!
D
Congruent to 0 mod 4, or 1 mod 4
Right on! Give the BNAT exam to get a 100% scholarship for BYJUS courses
Open in App
Solution
The correct option is D Congruent to 0 mod 4, or 1 mod 4 An n-vertex self-complementary graph has exactly half number of edges of the complete graph i.e. n(n−1)4~edges.
Since n(n - 1) must be divisible by 4, n must be congruent to 0 mod 4 or 1 mod 4.