Graph Theory: Finding the number of vertices

  • #1

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.)
 

Answers and Replies

  • #2
andrewkirk
Science Advisor
Homework Helper
Insights Author
Gold Member
3,933
1,496
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?
 
  • #3
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.
 
  • #4
ehild
Homework Helper
15,543
1,914
Y

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?
 
  • #5
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.
 
  • #6
ehild
Homework Helper
15,543
1,914
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?
 

Related Threads on Graph Theory: Finding the number of vertices

Replies
0
Views
6K
  • Last Post
Replies
9
Views
2K
  • Last Post
Replies
0
Views
915
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
0
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
0
Views
2K
  • Last Post
Replies
2
Views
942
Replies
0
Views
5K
Top