My Math Forum quantity of edges if graph k-regular?

 Computer Science Computer Science Forum

 May 1st, 2009, 08:41 AM #1 Newbie   Joined: May 2009 Posts: 2 Thanks: 0 quantity of edges if graph k-regular? hi all, how much edges does a graph (|V|=n) max. have, if all nodes have degree k ? (k-regular)
 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 k-regular? 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 k-regular? (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 k-regular?

Quote:
 Originally Posted by viktord (k*n)/2 ??? there is sometimes one edge missed
There is?!

In any graph, the following holds:

$2|E(G)|=\sum_{v\in V(G)}d(v)$.
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 Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post discretemath Applied Math 1 October 27th, 2012 09:10 PM Hangout Linear Algebra 7 May 30th, 2012 06:50 AM restin84 Applied Math 4 April 4th, 2012 01:12 PM tolmachevroman Applied Math 1 June 1st, 2011 06:00 AM Nekochan Applied Math 0 January 28th, 2011 12:39 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top