Proof: inequality involving vertices and edges of a graph

restin84 · April 3rd, 2012, 03:20 PM

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

octahedron · April 3rd, 2012, 03:47 PM

Little advice: when number of edges in graph is maximal each vertex is connected with n-1 vertices

restin84 · April 3rd, 2012, 07:10 PM

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?

octahedron · April 4th, 2012, 12:10 PM

If the inequality holds for maximal possible number of edges, it holds for every number.

restin84 · April 4th, 2012, 01:12 PM

Okay thanks

April 3rd, 2012, 03:20 PM	#1
restin84 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
$restin84 is offline$

April 3rd, 2012, 03:47 PM	#2
octahedron 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
$octahedron is offline$

April 4th, 2012, 12:10 PM	#4
octahedron 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.
$octahedron is offline$

April 4th, 2012, 01:12 PM	#5
restin84 Member Joined: Sep 2009 Posts: 71 Thanks: 0	Re: Proof: inequality involving vertices and edges of a grap Okay thanks
$restin84 is offline$

Thread Tools
$Show Printable Version$ Show Printable Version $Email this Page$ Email this Page
Display Modes
$Linear Mode$ Linear Mode $Hybrid Mode$ Switch to Hybrid Mode $Threaded Mode$ Switch to Threaded Mode

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 non-intersecting 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 k-regular?	viktord	Computer Science	3	May 2nd, 2009 02:13 PM