The problem I'm working on is:
Let $G$ be a simple graph with $v(G) = kp$ and $\delta(G) \geq kq$. Show that $G$ has a subgraph $F$ with $v(F) = p$ and $\delta(F) \geq q$.
Can anyone give me any hints? The reverse way makes sense because we just take $k$ copies of the graph and connect each point to all neighbors in each graph copy. I can't think of nay way of even starting for the problem at hand though.
Let $G$ be a simple graph with $\nu(G)=kp$ and $\delta(G)\ge kq$.
Given a partition $\{V_1,\dots,V_k\}$ of the vertex set $V=V(G)$, let $\varepsilon(V_1,\dots,V_k)$ denote the number of edges of $G$ joining vertices in different parts of the partition.
Choose a partition $\{V_1,\dots,V_k\}$ of $V$ into $k$ $p$-element sets which minimizes $\varepsilon(V_1,\dots,V_k)$ over all such partitions. I claim that at least one of the induced subgraphs $F_i=G[V_i]$ satisfies $\delta(F_i)\ge q$.
Let $I=\{1,\dots,k\}$. Assume for a contradiction that $\delta(F_i)\lt q$ for each $i\in I$. For each $i\in I$ choose a vertex $v_i\in V_i$ with $d_{F_i}(v_i)\lt q$. Since $d_G(v_i)\ge kq$, we can choose an index $f(i)\in I\setminus\{i\}$ so that $v_i$ is adjacent to at least $q+1$ vertices in $V_{f(i)}$.
Since $I$ is a nonempty finite set, and since the self-map $f:I\to I$ has no fixed points, it follows that $f$ contains a cyclic permutation of length $\ge2$; that is, for some $m\ge2$ there are $m$ distinct indices $i_1,\dots,i_m\in I$ such that $f(i_1)=i_2,\dots,f(i_{m-1})=i_m,f(i_m)=i_1$. We may assume that $(i_1,\dots,i_m)=(1,\dots,m)$; thus $f(1)=2,\dots,f(m-1)=m,f(m)=1$.
From the partition $\{V_1,\dots,V_k\}$ we obtain a new partition $\{V'_1,\dots,V'_k\}$ as follows: for each $i\in\{1,\dots,m\}$, the vertex $v_i$ is moved from $V_i$ to $V_{f(i)}$; nothing else is changed. In other words, we have $V'_1=(V_1\setminus\{v_1\})\cup\{v_m\}$, $V'_i=(V_i\setminus\{v_i\})\cup\{v_{i-1}\}$ for $2\le i\le m$, and $V'_i=V_i$ for $m\lt i\le k$. It is easy to see that $\varepsilon(V'_1,\dots,V'_k)\le\varepsilon(V_1,\dots,V_k)-m\lt\varepsilon(V_1,\dots,V_k)$, contradicting the assumed minimality of $\varepsilon(V_1,\dots,V_k)$.