My Math Forum Proof: inequality involving vertices and edges of a graph

 Applied Math Applied Math Forum

 April 3rd, 2012, 02:20 PM #1 Member   Joined: Sep 2009 Posts: 71 Thanks: 0 Proof: inequality involving vertices and edges of a graph I have a proof to do for school. Prove that in any simple graph G with n vertices and m edges, 2m <= n^2 - n I just need a little push in the right direction. I'm having trouble even coming up with a starting point. I also cannot find many problems similar to this one so that I may practice. A little advice would be appreciated
 April 3rd, 2012, 02:47 PM #2 Senior Member   Joined: Jul 2011 Posts: 118 Thanks: 0 Re: Proof: inequality involving vertices and edges of a grap Little advice: when number of edges in graph is maximal each vertex is connected with n-1 vertices
April 3rd, 2012, 06:10 PM   #3
Member

Joined: Sep 2009

Posts: 71
Thanks: 0

Re: Proof: inequality involving vertices and edges of a grap

Quote:
 Originally Posted by octahedron Little advice: when number of edges in graph is maximal each vertex is connected with n-1 vertices
But I could not really say that the number of edges in this particular graph is maximal could I? Do I need cases? Or is the fact that "the number of edges is maximal" in the inequality somehow?

 April 4th, 2012, 11:10 AM #4 Senior Member   Joined: Jul 2011 Posts: 118 Thanks: 0 Re: Proof: inequality involving vertices and edges of a grap If the inequality holds for maximal possible number of edges, it holds for every number.
 April 4th, 2012, 12:12 PM #5 Member   Joined: Sep 2009 Posts: 71 Thanks: 0 Re: Proof: inequality involving vertices and edges of a grap Okay thanks

 Tags edges, graph, inequality, involving, proof, vertices

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post eChung00 Applied Math 1 February 27th, 2013 02:40 AM discretemath Applied Math 1 October 27th, 2012 08:10 PM tolmachevroman Applied Math 1 June 1st, 2011 05:00 AM Nekochan Applied Math 0 January 28th, 2011 11:39 AM viktord Computer Science 3 May 2nd, 2009 01:13 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top