![]() |
|
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 n-1 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 | |
|
![]() | ||||
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 |