Given:Gis a simple (no loops or multiple edges) graph withnvertices.

The number of edges inGis at least , wheren>k.

Prove:Ghas minimum degree at leastk.

Unless I made a mistake, I have successfully proven that this is not true. Please help if you can (thank you).

Proof(so far): The sum of the degrees of all the vertices inGequals twice the number of edges inG(theorem from the previous chapter of the book):

The last term is the number of edges in a complete bipartite graph with independent setsAof sizek-1andBof size2n-k.

Sincen>k,2n-k>2k-k=k>k-1means that setBhas more vertices and thus lower degree. All the vertices inBhave degreek-1, or the minimum degree ofGisk-1.

So, this is probably wrong. First problem is that the wrong result. Second, who says thatGis a bipartite graph? Couldn't a graph of this many edges be of another form with lower minimum degree?

Also, who says that just because the sum of the degrees comes out to a number which looks like the number of edges in a specific type of graph that it means the graph is in that shape (yes, I did this on my own, so far, but wondering about my reasoning).

So, graph experts, where did I go wrong?

Thanks,

J