Graph Theory

Date: 09/29/2001 at 06:41:58
From: Kate Rogers
Subject: Graph Theory

Can you please explain to me briefly why a graph with five vertices 
each having a degree of 3 is not possible ?

Date: 09/30/2001 at 01:16:09
From: Doctor Jodi
Subject: Re: Graph Theory

Hi Kate,

It might help to draw some pictures of small graphs.

Degree 3 means that each vertex has three edges coming from it.  
Notice that each edge connects to exactly two vertices. So how many 
edges are there, if your graph has five vertices? There should be 
3 * 5/2 = 7 1/2 edges. 

Does this make sense?

But of course you can't have half edges, so this is impossible.

Write back if you have more questions.

- Doctor Jodi, The Math Forum
  http://mathforum.org/dr.math/