# Regular Graphs

• May 8th 2008, 10:39 AM
ccdelia7
Regular Graphs
Let G be an r-regular graph with n verticies and m edges. Find (& prove) a simple algebraic relation between r, n, & m.

Definition: r-Regular - all verticies have degree r.
• May 8th 2008, 10:50 AM
icemanfan
Quote:

Originally Posted by ccdelia7
Let G be an r-regular graph with n verticies and m edges. Find (& prove) a simple algebraic relation between r, n, & m.

Definition: r-Regular - all verticies have degree r.

A good place to start is that every edge increases the degree of two vertices by 1. That being the case, if the graph is r-regular, there must be an even number of edges. Let's examine cases where n = 4.

You could have r = 1, in which case there would be two edges (m = 2)
You could have r = 2, in which case there would be four edges (m = 4)
You could have r = 3, in which case there would be six edges (m = 6)

So it looks like the relationship is \$\displaystyle rn = 2m\$. Try it and you will see that it works for larger graphs as well. The proof hinges on the fact that every edge increases the degree of two vertices by 1.
• May 8th 2008, 11:10 AM
ccdelia7
Does it really work for r=1 - I would think there would be one edge in that case. Maybe I'm not looking at it right??(Doh)
• May 8th 2008, 11:13 AM
ccdelia7
Got it! you're right!! I was thinking differently for n verticies!! Thanks iceman!
• May 8th 2008, 12:09 PM
Plato
That answer seems to apply only to simple graphs. (See my other reply.)
It does not apply if by graph you mean that loops and multiple edges are allowed.