Finite graph and vertices.
Show that the vertices of any finite graph can be colored green and red so that at least half of the neighbors of every red vertex are green. Remember that the idea of this section is to look for a maximum or minimum. For full (or extra) credit prove it in that manner. You do not have to find the coloring, just prove that there must be one.