My Math Forum  

Go Back   My Math Forum > College Math Forum > Applied Math

Applied Math Applied Math Forum


Reply
 
LinkBack Thread Tools Display Modes
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
restin84 is offline  
 
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
octahedron is offline  
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?
restin84 is offline  
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.
octahedron is offline  
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
restin84 is offline  
Reply

  My Math Forum > College Math Forum > Applied Math

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 02:40 AM
bipartite graph, vertices, edges and arithmetics discretemath Applied Math 1 October 27th, 2012 08:10 PM
Graph with non-intersecting edges tolmachevroman Applied Math 1 June 1st, 2011 05:00 AM
Graph theory : coloring edges Nekochan Applied Math 0 January 28th, 2011 11:39 AM
quantity of edges if graph k-regular? viktord Computer Science 3 May 2nd, 2009 01:13 PM





Copyright © 2019 My Math Forum. All rights reserved.