Let $G$ be a simple graph with $n$ vertices and $m$ edges. Two vertices are called neighbours if there is an edge between them. It turns out the $G$ does not contain any cycles of length from 3 to $2k$ (inclusive), where $k\geq2$ is a given positive integer. a) Prove that it is possible to pick a non-empty set $S$ of vertices of $G$ such that every vertex in $S$ has at least $\left\lceil \frac mn \right\rceil$ neighbours that are in $S$. ($\lceil x\rceil$ denotes the smallest integer larger than or equal to $x$.) b) Suppose a set $S$ as described in (a) is chosen. Let $H$ be the graph consisting of the vertices in $S$ and the edges between those vertices only. Let $v$ be a vertex of $H$. Prove that at least $\left\lceil \left(\frac mn -1\right)^k \right\rceil$ vertices of $H$ can be reached by starting at $v$ and travelling across the edges of $H$ for at most $k$ steps. (Note that $v$ itself satisfies this condition, since it can be reached by starting at $v$ and travelling along the edges of $H$ for 0 steps.)
Problem
Source:
Tags: combinatorics, graph
02.05.2017 13:22
$\text {NOTATION :} $ $\mathbb V (X),\mathbb E (X) $ respectively denote the vertex set and edge set of any graph $X $. $d (v)$ denotes the degree of any vertex $v $. $\text {(a)} $ is true for any graph $G $. We need to prove that $\exists $ an induced subgraph $H $ of $G $ with the degree of each vertex $\geq \frac {m}{n} $. To meet this end, we introduce an algorithm. We shall start with our original graph $G $ and delete one vertex at each step to get successively smaller subgraphs of $G $ as follows $\text {ALGORITHM :} $ After $k$-th step, let the obtained subgraph be $G_k $. We shall delete a vertex $v\in\mathbb V (G_k) $ satisfying $d (v)< \frac {m}{n} $ to obtain the subgraph $G_{k+1} $. Observe that $|\mathbb V (G_k)|=(n-k)$. It is clear that the algorithm terminates in atmost $n $ steps. Let it terminate at the $t$-th step, where $t\leq n $. We shall prove that $t<n $. Then $|\mathbb V (G_t)|>0$ and we cannot perform our step $\implies d (v)\geq\frac {m}{n}\forall v\in\mathbb V (G_t) $. Then setting $H\equiv G_t $ serves our purpose. For any graph $X $ define a function $f $ such that $f (X)=\frac {|\mathbb E (X)|}{|\mathbb V (X)|}$. $\text {CLAIM :} $ $f (G_k)\geq \frac {m}{n}$. $\text {PROOF :} $ The proof is by induction. For $k=0$, equality clearly holds. Suppose the result is true for some $k$ and the step can be performed to obtain $G_{k+1} $. Then $|\mathbb {V}(G_{k+1})|=n-(k+1),|\mathbb {E}(G_{k+1})|\geq |\mathbb {E}(G_k)|-\frac {m}{n} $ as degree of deleted vertex is less than $\frac {m}{n} $. Thus $f (G _{k+1})\geq \frac {|\mathbb E (G_k)|-\tfrac {m}{n}}{n-(k+1)}$. By induction hypothesis $|\mathbb E (G_k)|\geq \frac {m}{n}|\mathbb V (G_k)|=\frac {m(n-k)}{n}$, substituting this into the inequality gives $f (G_{k+1})\geq \frac{m}{n} $; so we are done by induction. Suppose $t=n $. Then after $(n-1)$-th step we are left with the subgraph $G_{n-1}$ consisting of an isolated vertex $\implies f (G_{n-1})=0 <\frac {m}{n} $ which contradicts our $\text {CLAIM} $. Thus $t <n $ and the subgraph $G_t $ serves our purpose.