Register

GATE Overflow | Mock GATE | Test 1 | Question: 54

• retagged by
1,050 views
4 votes
4 votes

Let $S$ be a set of $n$ elements $\{1, 2, \dots n\}$ and $G$ a graph with $2^n$ vertices, where each vertex corresponds to a distinct subset of $S$. Two vertices are adjacent if the symmetric difference of the corresponding sets has exactly $2$ elements. Every vertex in $G$ has the same degree. What is the degree of a vertex in $G$ and how many connected component does $G$  have, respectively?

  1. $n, 3$
  2. $(n(n-1))/2,2$
  3. $1, n$
  4. $n+1, n$
• retagged by
User Avatar

1 Answer

9 votes
9 votes

Sorry for bad handwriting

User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

2 votes
2 votes
4 answers
1
Ruturaj Mohanty asked Dec 27, 2018
2,150 views
GATE Overflow | Mock GATE | Test 1 | Question: 34
Let $G$ be a graph of order $n$ in which every vertex has degree equal to $d$. How large must $d$ be in order to guarantee that $G$ is connected? $\frac{n}{2}$ $\lceil (n-1)/2 \rceil$ $\lfloor (n+1)/2 \rfloor$ $(n-1)/2$
Let $G$ be a graph of order $n$ in which every vertex has degree equal to $d$. How large must $d$ be in order to guarantee that $G$ is connected?$\frac{n}{2}$$\lceil (n-1...
User Avatar
6 votes
6 votes
1 answer
2
Ruturaj Mohanty asked Dec 27, 2018
3,302 views
GATE Overflow | Mock GATE | Test 1 | Question: 35
Consider the following graph. How many paths of length $4$ exist from node $A$ to node $D$? (Note: The path may have repeated vertices. You can think of it as walks in general rather than path)
Consider the following graph.How many paths of length $4$ exist from node $A$ to node $D$?(Note: The path may have repeated vertices. You can think of it as walks in gene...
User Avatar
5 votes
5 votes
1 answer
3
Ruturaj Mohanty asked Dec 27, 2018
1,269 views
GATE Overflow | Mock GATE | Test 1 | Question: 51
... given adjacency matrix representation of a graph containing $7$ nodes (namely A , B, C, D, E, F, G). The Chromatic number of the given graph is?
$\begin{array}{|c|c|c|c|c|c|c|} \hline 0 & 1 & 1 & 0 & 1 & 1 & 0 \\ \hline 1 & 0 & 0 & 1 & 1 & 0 & 1 \\ \hline 1& 0 & 0 & 1 & 1 & 1 & 0 \\ \hline 0 & 1 & 1 & 0 & 1 & 0 & ...
User Avatar
Link Copied!