Register

GATE Overflow Test Series | Discrete Mathematics | Test 4 | Question: 12

• recategorized by
204 views
2 votes
2 votes

Consider the following two statements with respect to a group of $9$ people:

  • $S_1:$ It is possible for everyone to be friends with exactly $2$ others in the group
  • $S_2:$ It is possible for everyone to be friends with exactly $3$ others in the group

Which of the above two statements is/are TRUE?

  1. $S_1$ only
  2. $S_2$ only
  3. Both $S_1$ and $S_2$
  4. Neither $S_1$ nor $S_2$
• recategorized by
User Avatar

1 Answer

Best answer
2 votes
2 votes
$S_1$ is true as we can form a cycle graph of $9$ vertices each representing a person.

$S_2$ is not possible as this will mean a graph of $n$ vertices each having a degree $3$ giving the sum of degrees $ = 9\times 3 = 27.$ Since the sum of degrees in a graph must be even, this is not valid.
• selected by
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

1 votes
1 votes
1 answer
1
gatecse asked Sep 14, 2020
130 views
GATE Overflow Test Series | Discrete Mathematics | Test 4 | Question: 7
Suppose a simple graph has $45$ edges, $5$ vertices of degree $6$, and all others of degree $5$. How many vertices does the graph have?
Suppose a simple graph has $45$ edges, $5$ vertices of degree $6$, and all others of degree $5$. How many vertices does the graph have?
User Avatar
1 votes
1 votes
1 answer
2
gatecse asked Sep 14, 2020
195 views
GATE Overflow Test Series | Discrete Mathematics | Test 4 | Question: 1
If $G$ is a simple graph with $16$ edges and $\overline{G}$ has $12$ edges, how many vertices does the complement graph $\overline{G}$ have?
If $G$ is a simple graph with $16$ edges and $\overline{G}$ has $12$ edges, how many vertices does the complement graph $\overline{G}$ have?
User Avatar
4 votes
4 votes
1 answer
3
gatecse asked Sep 14, 2020
321 views
GATE Overflow Test Series | Discrete Mathematics | Test 4 | Question: 3
The number of possible connected simple graphs with $3$ labelled vertices is ________
The number of possible connected simple graphs with $3$ labelled vertices is ________
User Avatar
Link Copied!