The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

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   
Associated Topics:
High School Discrete Mathematics
High School Equations, Graphs, Translations

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.