54 views

Let $G$ be a simple undirected graph having $n$ vertices with the property that the average of the degrees of the vertices in $G$ is at least $4.$ Consider the following procedure:

$\textsf{Repeatedly delete a vertex from G whose degree is at most 2, until there is no such vertex}.$

Let $H$ be the resulting graph at the end of this procedure. Then,

1. Show that the graph $H$ is not empty.
2. Using part $\textsf{(i)}$ above, prove that there exist four distinct vertices $\textsf{a}, \textsf{b}, \textsf{c}$ and $\textsf{d}$ in $H$ such that $\textsf{deg(a)} = \textsf{deg(b)}$ and $\textsf{deg(c)} = \textsf{deg(d)},$ where $\textsf{deg(x)}$ denotes the degree of the vertex $\textsf{x}$.