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!

Homework Help: Graph theoretical problems

  1. Jan 28, 2015 #1
    1. The problem statement, all variables and given/known data
    #1 Does there exist a graph that has m times more edges than vertices?
    #2 How to calculate the number of possible graphs given the number of vertices and edges? Connected graphs, disconnected graphs.

    2. Relevant equations

    3. The attempt at a solution
    #1We know that a complete graph has [itex]\frac{n(n-1)}{2}[/itex] number of edges, n being the number of vertices in the complete graph. Hence [itex] m = \frac{n-1}{2} \Leftrightarrow n = 2m + 1[/itex].

    How to approach this problem if one has no knowledge of complete graphs having [itex]\frac{n(n-1)}{2}[/itex] edges?
    #2 A connected graph is such a graph whose every 2 vertices can be connected via a path.
    If we have, say, 5 vertices and 7 edges.

    Well, from the complete graph we know there are total of [itex]\frac{n(n-1)}{2}[/itex] edges and we have to use 7.
    It would be 10 choose 7 graphs - but are they all connected?
  2. jcsd
  3. Jan 28, 2015 #2


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    It's not something you need prior knowledge of. You only need to find one example. If you start in the obvious way, looking for an example in which every vertex has r edges, it is easy to see that r =2m and should be apparent that a graph of r+1 vertices all interconnected is an example.
    That's a very hard problem, unless you are supposed to regard the vertices as distinct. In which case, the question would have been better worded as the number of graphs with m edges that can be formed on n labelled vertices.
    Not sure what this clause means. Does it mean counting those cases separately or counting them all together? You have interpreted it as separately, so I'll assume that's right.
    Clearly they aren't necessarily all connected in general. For 5 vertices and 7 edges, they will all be connected. (Suppose such a graph is not connected, falling into k and n-k vertex sets. What's the maximum number of edges?) But for 4 to 6 edges on 5 vertices there can be both connected and disconnected graphs.
    Sounds like an application of inclusion-exclusion.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted