1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Graph Theory: Finding the number of vertices

  1. Jan 29, 2016 #1
    1. The problem statement, all variables and given/known data
    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.

    2. Relevant equations

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

    3. The attempt at a solution

    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.)
     
  2. jcsd
  3. Jan 29, 2016 #2

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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?
     
  4. Jan 29, 2016 #3

    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.
     
  5. Jan 29, 2016 #4

    ehild

    User Avatar
    Homework Helper
    Gold Member

    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?
     
  6. Jan 29, 2016 #5
    Okay, you're right some of my answers for c don't make sense. But neither do 10 or 40.
     
  7. Jan 29, 2016 #6

    ehild

    User Avatar
    Homework Helper
    Gold Member

    The book is wrong.
    What is your answer to question c?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted