My Math Forum  

Go Back   My Math Forum > Science Forums > Computer Science

Computer Science Computer Science Forum


Reply
 
LinkBack Thread Tools Display Modes
May 1st, 2009, 07: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)
viktord is offline  
 
May 1st, 2009, 08:32 AM   #2
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
May 2nd, 2009, 01: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
viktord is offline  
May 2nd, 2009, 01: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:

.
Where d(v) is the degree of each vertex.
Try proving that. It's a straightforward counting argument.
cknapp is offline  
Reply

  My Math Forum > Science Forums > Computer Science

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 08:10 PM
Scaling a 2D object along one if its edges Hangout Linear Algebra 7 May 30th, 2012 05:50 AM
Proof: inequality involving vertices and edges of a graph restin84 Applied Math 4 April 4th, 2012 12:12 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





Copyright © 2019 My Math Forum. All rights reserved.