
Computer Science Computer Science Forum 
 LinkBack  Thread Tools  Display Modes 
May 1st, 2009, 08:41 AM  #1 
Newbie Joined: May 2009 Posts: 2 Thanks: 0  quantity of edges if graph kregular?
hi all, how much edges does a graph (V=n) max. have, if all nodes have degree k ? (kregular) 
May 1st, 2009, 09:32 AM  #2 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: quantity of edges if graph kregular?
Each vertex has k edges. If you count the edges for each vertex, every edge will be counted twice.

May 2nd, 2009, 02:24 AM  #3 
Newbie Joined: May 2009 Posts: 2 Thanks: 0  Re: quantity of edges if graph kregular?
(k*n)/2 ??? there is sometimes one edge missed 
May 2nd, 2009, 02:13 PM  #4  
Senior Member Joined: Oct 2007 From: Chicago Posts: 1,701 Thanks: 3  Re: quantity of edges if graph kregular? Quote:
In any graph, the following holds: . Where d(v) is the degree of each vertex. Try proving that. It's a straightforward counting argument.  

Tags 
edges, graph, kregular, quantity 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
bipartite graph, vertices, edges and arithmetics  discretemath  Applied Math  1  October 27th, 2012 09:10 PM 
Scaling a 2D object along one if its edges  Hangout  Linear Algebra  7  May 30th, 2012 06:50 AM 
Proof: inequality involving vertices and edges of a graph  restin84  Applied Math  4  April 4th, 2012 01:12 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 