d-regular, planar, 2-colored graph

VanDelay · **Joined:** Wed, 29 Sep 2010 22:33:04 UTC **Posts:** 2

Hey.

Find the values of d for which a d-regular, planar, 2-colored (coloring the vertices) graph exists.

If the graph is planar, then $m\leq3(n-2)$ (where m = number of edges, n = number of vertices).
Also, $m = \frac{nd}{2}$ (because of the d-regularity).
From the two above i can say that d < 6 (i'm not so sure of that either).

Can someone help?
thanks

outermeasure · **Posted:** Thu, 30 Sep 2010 04:46:55 UTC

VanDelay wrote:

Hey.

Find the values of d for which a d-regular, planar, 2-colored (coloring the vertices) graph exists.

If the graph is planar, then $m\leq3(n-2)$ (where m = number of edges, n = number of vertices).
Also, $m = \frac{nd}{2}$ (because of the d-regularity).
From the two above i can say that d < 6 (i'm not so sure of that either).

Can someone help?
thanks

Right, so what remains is for you to show that each of d=1,2,3,4,5 is possible (or not).

(By the way, if you allow infinite graphs you have to consider $d\geq 6$ too.)

VanDelay · **Joined:** Wed, 29 Sep 2010 22:33:04 UTC **Posts:** 2

I think i solved it (it's only for finite graphs), if anyone's intrested:

The d=1 case is easy (just two connected vertices).

For d>1:
We know that $m = \frac{nd}{2} > n - 1$ , so there must be at least one cycle within. Since the graph is 2-colored, we know that there are no cycles of odd length, so the girth (size of the smallest cycle) is 4 (or greater).

If we put g=4 and $m = \frac{nd}{2}$ in $\frac{g}{g-2}(n-2) \geq m$ :
$2(n-2) \geq \frac{nd}{2}$
$n(2-\frac{d}{2}) \geq 2$
$=> 2 -\frac{d}{2} > 0$
d < 4

Now this tells us that graphs with d>=4 don't exist (We still need to find those with d=2,3).
The 2-regular is a square and 3-regular is a cube (so that there's no intersection between edges).

S.O.S. Mathematics CyberBoard

d-regular, planar, 2-colored graph

Who is online