Let S be a set of n elements {1, 2, …, n} and G a graph with 2ⁿ vertices, each…

PYQ GATE 2000

Let S be a set of n elements {1, 2, …, n} and G a graph with 2ⁿ vertices, each vertex corresponding to a distinct subset of S. Two vertices are adjacent iff the symmetric difference of the corresponding sets has exactly 2 elements. Note: The symmetric difference of two sets R₁ and R₂ is defined as (R₁ \ R₂) ∪ (R₂ \ R₁). (a) Every vertex in G has the same degree. What is the degree of a vertex in G? (b) How many connected components does G have?

Attempted by 1 students.

Sign up free to check your answer

Sign up free

Explore the full course: Zero To Hero

Loading lesson…