236 views

Let $G$ be an undirected graph with $n$ vertices. For any subset $S$ of vertices, the set of neighbours of $S$ consists of the union of $S$ and the set of vertices $S'$ that are connected to some vertex in $S$ by an edge of $G$. The graph $G$ has the nice property that every subset of vertices $S$ of size at most $n/2$ has at least $1.5 |S|$-many neighbours. What is the length of a longest path in $G$?

1. $O (1)$
2. $O (\log \log n)$ but not $O (1)$
3. $O (\log n)$ but not $O (\log \log n)$
4. $O \left(\sqrt{n}\right)$ but not $O (\log n)$
5. $O (n)$ but not $O \left(\sqrt{n}\right)$

I have one doubt in statement -->

S of size at most n/2 has at least 1.5|S|-many neighbors.

Let us say S = n/2 then it has 3/2(n) neighbor but n < = (1/2)n + (3/2)n is a contradiction. Please correct me if i am wrong.

Here we have to find the longest path in Graph.

Let's start with 1 node(chose any one)  & find the number of hops in which whole Graph is reachable i.e. all the n vertices are reachable.

From First node (say A) -

(1) within 1 hop(1 edge traversal)  we can reach atleast       =     3/2    nodes

{as neighbourhood of A has atleast 3/2 nodes}

(2) within 2 hops we can reach atleast           $\left (\frac{3}{2} \right )^2$  nodes

(3) within 3 hops we can reach atleast           $\left (\frac{3}{2} \right )^3$  nodes

and so on.. like this when our nodes reach $\left ( \frac{n}{2} \right )$ within 1 more hop we can reach upto $\left ( \frac{n}{2} \right ) * \frac{3}{2} = \frac{3n}{4}$ nodes..

uptill here we will take O(log n) hops {to reach $\frac{3n}{4}$ nodes}.

But this property is valid upto a subset of size atmost n/2 .. so, here I stuck to proceed..

Hope it helps.. Also any suggestions to proceed further are welcome..

it says n/2 can have at least 1.5(s) which means at most this graph can become complete graph, and in that case path length will be O(n).

how does it mean that " 1.5(s) " mean complete graph ?

at least 1.5(s), at most it can be anything. 1.5(s) is lower bound ex: if we consider n/2 set then it will have at least n/4 neighbors, whereas these n/4 neighbors will surely have at least 2(n/4) neighbors
So, according to you O(n) should be correct ?