The $2^{n}$ vertices of graph G correspond to all subsets a set of size n, for $n \geq 6.$ Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements.

The number of vertices of degree zero in G is

No worries! We‘ve got your back. Try BYJU‘S free classes today!

n + 1

Right on! Give the BNAT exam to get a 100% scholarship for BYJUS courses

2^{n}

No worries! We‘ve got your back. Try BYJU‘S free classes today!

Open in App

Solution

The correct option is C n + 1
Let S contains n elements then S have $2^{n}$ subsets. Graph G contains $2^{n}$ vertices.

Let $S = {v_{1}, v_{2}, . . . ., v_{n}} .$ Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements.

So $| {V_{i}} \cap {V_{j}} | = 2$

For this to happen, the subset must have at least 2 elements.

There are n sets which contains a single elements for $V_{1} to V_{n}$ who doesn't intersect another set such that it contains two elements. Therefore the degree of all these n vertices is zero. G also contains a vertex $ϕ$ whose degree is zero. So the number of vertices whose degree is zero is n + 1.

Suggest Corrections

Similar questions

The $2^{n}$ vertices of graph G correspond to all subsets a set of size n, for $n \geq 6.$ Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements.

The maximum degree of a vertex in G is

Q. Let G be a graph with 100! vertices, with each vertex labelled by a distinct permutation of the numbers 1, 2, ... 100. there is an edge between vertices u and v if and only if the label of u can be obtained by swapping two adjacent numbers in the label of v. Let y denote the degree of a vertex in G and z denote the number of connected components in G.
Then, y + 10z =

Q. G is a simple, connected, undirected graph. Some vertices of G are of odd degree. Add a node v to G and make it adjacent to each odd degree vertex of G The resultant graph is sure to be

Q. G is a graph on n vertices and 2n - 2 edges. The edges of G can be partitioned into two edge-disjiont spanning trees. Which of the following is NOT true for G ?

Join BYJU'S Learning Program

The 2n vertices of graph G correspond to all subsets a set of size n, for n≥6. Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements. The number of vertices of degree zero in G is

The $2^{n}$ vertices of graph G correspond to all subsets a set of size n, for $n \geq 6.$ Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements.

The number of vertices of degree zero in G is