edited by
1,125 views
2 votes
2 votes

Let $G$ be an arbitrary graph on $n$ vertices with $4n − 16$ edges. Consider the following statements:

  1. There is a vertex of degree smaller than $8$ in $G$.
  2. There is a vertex such that there are less than $16$ vertices at a distance exactly $2$ from it.

Which of the following is true:

  1. I Only
  2. II Only
  3. Both I and II
  4. Neither I nor II
     
edited by

2 Answers

0 votes
0 votes

Answer will be (C) Both $I$ and $II$ are correct 

For $I$ :

Lets assume that every vertex has degree 8 (Just to check whether possible or not)

By Handshaking Theorem ,

We have LHS =$\sum deg(v_{i})$ = 8*n

and RHS = 2$e$ = $2(4n-16)$=$8(n-4)$    [Now this is always true as the number of edges has been provided]

Now in order to make the LHS equal to the RHS there must be a vertex(or vertices) whose degree should be less than 8 hence $I$ is true.

For $II$

Lets take an example,

Let n=5 then No. of edges = $4n-16$=$4$ which is also equal to $n-1$ 

Hence it forms a tree(Suppose), then $II$ is also true as there exist a vertex such that there are less than 16 vertices at distance exactly 2 from it.

Tree with 5 vertices

Answer:

Related questions

2 votes
2 votes
3 answers
3
8 votes
8 votes
2 answers
4
Tesla! asked Feb 4, 2018
1,105 views
An FM radio channel has a repository of $10$ songs. Each day, the channel plays $3$ distinct songs that are chosen randomly from the repository.Mary decides to tune in to...