CMI2017-A-05

Question

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:

• A. I Only
• B. II Only
• C. Both I and II
• D. Neither I nor II
   

Answer 1

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.

Comments

No, its incorrect method, how can you assume things like degree of each vertex are 8 and the end result doesn't make any sense.

---

Now, this is the official solution to the problem.

I guess for (I) the assumption that I made is similar to the pigeon hole principle they used.However for (II), no constraint on 'n' was given further I also stressed on the 'there exists' criteria so I thought of this example. 

Anyways, if possible can you explain the pigeon hole method in detail and why my method for (II) is incorrect.

---

II There is a vertex such that there are less than 16 vertices at distance exactly 2 from it.

 This is not true for all the graphs like for n=100 e=384 Graph may be connected or disconnected there are various possibilities regarding the structure of graph and some of them may fulfil statement II but not all so if anything is not true for all case we cannot say its tautology.

For the first part, I didn't understand there or your approach so I came up with this theory minimum edges required so that graph can be connected is n-1 and sufficient edges required to assure graph is connected is C(n-1,2) so given graph lies between this 2 constraints with more on side of minimally connected thus we can make say if graph is connected then surely it has vertex having degree less then 8 because average degree of each vertex comes out to be 4., and no need to prove for disconnected graph

---

That’s proof y contradiction.

Answer 2

Comments

Hi @soujanyareddy13, could you kindly explain the 2^nd part in detail ? From when they connect k-1 vertices to k+3 equally spaced vertices .