
Applied Math Applied Math Forum 
 LinkBack  Thread Tools  Display Modes 
April 3rd, 2012, 03: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, 03: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 n1 vertices

April 3rd, 2012, 07:10 PM  #3  
Member Joined: Sep 2009 Posts: 71 Thanks: 0  Re: Proof: inequality involving vertices and edges of a grap Quote:
 
April 4th, 2012, 12:10 PM  #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, 01: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  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Proof involving inequality!  eChung00  Applied Math  1  February 27th, 2013 03:40 AM 
bipartite graph, vertices, edges and arithmetics  discretemath  Applied Math  1  October 27th, 2012 09:10 PM 
Graph with nonintersecting edges  tolmachevroman  Applied Math  1  June 1st, 2011 06:00 AM 
Graph theory : coloring edges  Nekochan  Applied Math  0  January 28th, 2011 12:39 PM 
quantity of edges if graph kregular?  viktord  Computer Science  3  May 2nd, 2009 02:13 PM 