Given: G is a simple (no loops or multiple edges) graph with n vertices.
The number of edges in G is at least , where n>k.
Prove: G has minimum degree at least k.
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 in G equals twice the number of edges in G (theorem from the previous chapter of the book):
The last term is the number of edges in a complete bipartite graph with independent sets A of size k-1 and B of size 2n-k.
Since n>k, 2n-k>2k-k=k>k-1 means that set B has more vertices and thus lower degree. All the vertices in B have degree k-1, or the minimum degree of G is k-1.
So, this is probably wrong. First problem is that the wrong result. Second, who says that G is 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