28 votes 28 votes A graph is self-complementary if it is isomorphic to its complement. For all self-complementary graphs on $n$ vertices, $n$ is A multiple of 4 Even Odd Congruent to 0 $mod$ 4, or, 1 $mod$ 4. Graph Theory gatecse-2015-set2 graph-theory graph-isomorphism out-of-syllabus-now + – go_editor asked Feb 12, 2015 • retagged Aug 2, 2015 by Arjun go_editor 13.9k views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply shashankrustagi commented Jan 12, 2021 reply Follow Share An n-vertex self-complementary graph has exactly half number of edges of the complete graph, i.e., n(n − 1)/4 edges, and (if there is more than one vertex) it must have diameter either 2 or 3.[1] Since n(n −1) must be divisible by 4, n must be congruent to 0 or 1 mod 4; for instance, a 6-vertex graph cannot be self-complementary. wikipedia 1 votes 1 votes Nirmalbbll commented Aug 15, 2021 reply Follow Share n(n-1)/4 means either n is divisible by 4 or (n-1) is divisible by 4 If n is divisible by 4 means n = 0 mod 4 If (n-1) is divisble by 4 means (n-1) = 0 mod 4 n = 1 mod 4 3 votes 3 votes Please log in or register to add a comment.
Best answer 59 votes 59 votes Ans D $E(G) + E(G') = \frac{n(n-1)}{2}$, where $E(G)$ denotes the no. of edges in $G$. ($G + G'$ will be a complete graph) for self complementary graphs, $E(G) = E(G')$ $E(G) = \frac{n(n-1)}{4}$ Vikrant Singh answered Feb 12, 2015 • edited Feb 18, 2015 by Arjun Vikrant Singh comment Share Follow See all 4 Comments See all 4 4 Comments reply smartmeet commented Jan 25, 2017 reply Follow Share 1why this is out-of-syllabus-now? 5 votes 5 votes dopey2020 commented May 23, 2020 reply Follow Share Can Someone explain this part---- "Since must be divisible by , it follows that or ?? 0 votes 0 votes Shivateja MST commented Jan 12, 2021 reply Follow Share Is this topic in syllabus ? 0 votes 0 votes shashankrustagi commented Jan 12, 2021 reply Follow Share yes it is 0 votes 0 votes Please log in or register to add a comment.
18 votes 18 votes By definition, a self-complementary graph must have exactly half the total possible number of edges, i.e., edges for a self-complementary graph on vertices. Since must be divisible by , it follows that or . Answer: D. Congruent to , or, . Source: Self-Complementary Graph -- from Wolfram MathWorld Shyam Singh answered Feb 18, 2015 Shyam Singh comment Share Follow See all 0 reply Please log in or register to add a comment.
4 votes 4 votes Ans: D because for self complimentary graphs, no. of vertices should be of the form 4k or 4k+1 astroaditya answered Jun 20, 2015 astroaditya comment Share Follow See all 2 Comments See all 2 2 Comments reply tiger commented Jan 18, 2016 reply Follow Share ok ans is D , but what option A means ? ie A multiple of 4 ? 3 votes 3 votes astroaditya commented Sep 9, 2018 reply Follow Share Because multiple of 4 does not suffice the condition of 4K + 1 1 votes 1 votes Please log in or register to add a comment.
0 votes 0 votes This question can be answered without any knowledge of formulas too by considering two examples as below : A cycle of size 5 which become a star like graph again resulting in the same. A graph with 4 vertices {1, 2, 3, 4}and edges (1, 2) and (3, 4). soham04 answered Apr 3, 2021 soham04 comment Share Follow See all 0 reply Please log in or register to add a comment.