Graph Theory: Finding the number of vertices

UltimateSomni
Messages
62
Reaction score
0

Homework Statement


1. How many vertices will the following graphs have if they contain:
(a) 12 edges and all vertices of degree 3.
(b) 21 edges, three vertices of degree 4, and the other vertices of degree 3.
(c) 24 edges and all vertices of the same degree.

Homework Equations



"Theorem 1
In any graph, the sum of the degrees of all vertices is equal to twice the number of
edges."

The Attempt at a Solution


[/B]
a) 12*2=24
3v=24
v=8
(textbook answer: 12)

b)
21*2=42

3*4 + 3v = 42
12+3v =42
3v=30
v=10
add the other 3 given vertices, and the total number of vertices is 13
(textbook answer: 9)

c) 24*2=48
48 is divisible by 1,2,3,4,6,8,12,16,24,48
Thus those would be the possible answers

(textbook answer: 8 or 10 or 20 or 40.)
 
Physics news on Phys.org
Your reasoning looks sound.
The book's answers do not seem to match the questions.
This is easiest to see for (c), as a 24-sided polygon has 24 edges and 24 vertices of degree 2. That 24-gon satisfies the question but 24 is not amongst the book's list of possible values.
Is it possible that there is more to the question than can be seen here? Is the statement of the question in the OP exactly the same as in the book?
 
andrewkirk said:
Your reasoning looks sound.
The book's answers do not seem to match the questions.
This is easiest to see for (c), as a 24-sided polygon has 24 edges and 24 vertices of degree 2. That 24-gon satisfies the question but 24 is not amongst the book's list of possible values.
Is it possible that there is more to the question than can be seen here? Is the statement of the question in the OP exactly the same as in the book?
I copy pasted it. I mean none of the book really makes any sense. It seems you're better off flipping a coin or using a random number generator than figuring it out.
 
Y
UltimateSomni said:

Homework Statement


1. How many vertices will the following graphs have if they contain:
(a) 12 edges and all vertices of degree 3.
(b) 21 edges, three vertices of degree 4, and the other vertices of degree 3.
(c) 24 edges and all vertices of the same degree.

Homework Equations



"Theorem 1
In any graph, the sum of the degrees of all vertices is equal to twice the number of
edges."

The Attempt at a Solution


[/B]
a) 12*2=24
3v=24
v=8
(textbook answer: 12)

b)
21*2=42

3*4 + 3v = 42
12+3v =42
3v=30
v=10
add the other 3 given vertices, and the total number of vertices is 13
(textbook answer: 9)

c) 24*2=48
48 is divisible by 1,2,3,4,6,8,12,16,24,48
Thus those would be the possible answers

(textbook answer: 8 or 10 or 20 or 40.)
a and b look correct but there are some limits for the number of edges and the degree in a graph of N nodes. I think the book meant simple graphs. How do you imagine a graph with 1 vertex and 24 edges?
 
ehild said:
Y

a and b look correct but there are some limits for the number of edges and the degree in a graph of N nodes. I think the book meant simple graphs. How do you imagine a graph with 1 vertex and 24 edges?
Okay, you're right some of my answers for c don't make sense. But neither do 10 or 40.
 
UltimateSomni said:
Okay, you're right some of my answers for c don't make sense. But neither do 10 or 40.
The book is wrong.
What is your answer to question c?
 
Back
Top