Let G V E be a graph with average degree D Show that there

Let G = (V, E) be a graph with average degree D. Show that there exists a subgraph H in G with delta(H) greaterthanorequalto that is, the minimum degree in H is at least D/2.

Solution

Take K4 where the average degree is 3. If I remove the vertex of smallest degree (they\'re all the same so it doesn\'t matter), then the average degree becomes 2.

Take C4 where the average degree is 2. If I remove the vertex of smallest degree (again, they\'re all the same), then the average degree is 4/3.

Take P4 where the average degree is 3/2. If I remove a vertex of degree 1, then the average degree becomes 4/3, which is smaller.

So, we would say that the average degree gets smaller or stays the same as I remove a vertex.

So, we make that claim, that we can therefore delete vertices (smallest first and move on from there) until I am left with a subgraph whose minimal degree >d/2.

If not, then my proof could be something like this: Determine the minimal degree of graph G. If it is >d/2, since a graph is a subgraph of itself, we\'re done, If the minimal degree is less than d/2, delete the vertex in G with the smallest degree, call it v1. Determine if the minimal degree of the graph G-v1 is >d/2. If it is, since G-v1 is a subset of G, we\'re done. If not, delete the vertex in G-v1 with the smallest degree, call it v2.

Again, if G-v1-v2 has a minimal degree of >d/2, we\'re done.

If not, repeat the process above until you are left with a graph which is a subgraph of G and has a minimal degree of >2.