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 freeLoading lesson…

