Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

Integral

  • 4 years ago

Sigh let's try this again: Let G be a connected regular graph with n edges. How many vertices can G have?

  • This Question is Closed
  1. Integral
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    A graph which is connected in the sense of a topological space, i.e., there is a path from any point to any other point in the graph.

  2. benice
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    the most vertices it can have is n-1

  3. Integral
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Can you post your reasoning please?

  4. benice
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    sorry n+1

  5. benice
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    actual the graph is regular so it n

  6. benice
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    the min would be a fully connected graph

  7. benice
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    |dw:1332551750259:dw|

  8. Integral
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    |dw:1332551852360:dw|

  9. Integral
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Doesn't regular mean no loops or repeated edges?

  10. benice
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    see i dont think that graph is regular a regular means each vertex has the same number of edges as every other vertex

  11. Integral
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Ohhh

  12. Integral
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    So a regular connected graph would have to be a cycle if the number of vertices is greater than 2?

  13. Integral
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    a simple graph whose vertices all have the same degree r.

  14. Integral
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Yes you're right.

  15. benice
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    for a fully connected is regular as each vertix has the max number of edges so for a given number of vertices ie t the number of edges (t)(t-1)/2

  16. benice
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    5 vertices fully connected is 10 6 vertices ..... 15 .. so

  17. Integral
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    wait you lost me

  18. benice
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    there is a min and the max .. .we got the max ... the min is a fully connected graph so if we were give 10 edges |dw:1332552333694:dw| we know it has 5 vertice but what would happen if we had 14 edges

  19. benice
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    for n edges the degree count is n*2 so the max is n*2/2 and the min is the number which leaves no remainder n*2/deg(x) x regular grpah

  20. benice
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    sorry about the confusion in technical terms it's been a while

  21. benice
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    so if we had 15 edges the toatal degrees would be 30 the max number of vertices is 15 with each degree 2 the min would be 6vertices with each degree 5

  22. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy