Let G be a graph with 15 vertices and 4 connected components. Prove that G has at least one component with at least 4 vertices. What is the largest number of vertices that a component of G can have?
Read over connected components for a long time and still have no idea how to prove this.
For the first, think about the pigeonhole principle. If each component has three vertices or less, how many vertices can there be? For the second, you want three of the components to have as few vertices as possible to leave as many as possible for the big one.