GATE 2015 CS (CS2) – Question 61

Engineering Mathematics · Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) · 2 marks · Multiple choice

A self-complementary graph is isomorphic to its complement. What must its vertex count n satisfy?

A multiple of 4
Even
Odd
Congruent to 0 or 1 modulo 4

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) Congruent to 0 or 1 modulo 4

Explanation

Such a graph and its complement have equal edge counts, so each has half of n(n−1)/2, namely n(n−1)/4. This must be an integer. Consecutive residues make n(n−1) divisible by four exactly when n≡0 or 1 mod 4. Thus D.

More Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions

GATE 2015 CS (CS2) Q62 – A bridge is an edge whose removal disconnects a connected graph. Which is true?
GATE 2026 CS (CS1) Q55 – An undirected, unweighted, simple graph G(V, E) is said to be 2-colorable if there exists…
GATE 2026 CS (CS2) Q36 – Consider a complete graph K n with n>4 vertices. Each spanning tree of K n is represented…
GATE 2024 CS (CS1) Q34 – The number of spanning trees in a complete graph of 4 vertices labelled A, B, C, and D is
GATE 2024 CS (CS1) Q51 – The chromatic number of a graph is the minimum number of colours used in a proper…
GATE 2024 CS (CS2) Q17 – Let A be the adjacency matrix of a simple undirected graph G. Suppose A is its own…

All Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions →