Results 1 to 14 of 14

Math Help - Labeling graph problem..

  1. #1
    Junior Member
    Joined
    Jun 2010
    From
    Skopje
    Posts
    54

    Labeling graph problem..

    Hi i was doing some exercises and i found this one bit shaky:

    i had to find the total number of graphs given the labels for all the vertices (graphs with edges starting from 1 till complete graph), actually the formula was given i needed to prove it, the formula is this : 2^(n(n-1)/2) if V(G) = n, so to prove this i used math. induction starting with base cases for n = 1,2,3 then i predicted that for n=k this term 2^(k(k-1)/2) is true, and for inductive step for n=k+1 i simply look at it this way: take off the k+1-th vertex and you get graph with k vertices for which the term is true, then if you consider the fact that after adding the k+1-th vertex you have 2 ways to name that vertex with the first from the k vertices and plus 2 ways to name it with the 2 vertex from the k vertices and so on till the k-th vertex, but this holds only for the particular graph i.e. for the graph that is let's say m edged, well if you take all the 2^(k(k-1)/2) graphs and do the same logic you get 2^(k(k-1)/2) * 2^k graphs for k+1 vertices , which after some algebraic restructuring comes to be 2^k(k+1)/2, now if you try the original formula 2^n(n-1)/2 and sub. n = k+1 you get the same exact thing as found in the previous logic.. so this is the prove i guess, that was part 1 from the task now the prob is the second part of the task which asks to give the number of graphs from those 2^n(n-1)/2 that contain m edges, so i came up with some ideas but they don't apply for the problem, my idea was to take combinations (n 2*m), the idea is to pick 2*m vertices from the n given and construct the edges but there's problem since in the graph there may be edges that are incident so then the logic 2 vertex per edge doesn't apply here, or else there might be pair of 2 groups of incident edges that them selfs are not incident either with vertices or edges, like you have _._._ . _._._ , so the graph has 5 vertices and 2 groups (subsets) of edges that per group are incident but between those group there's no edge connection (actually graph by components)..

    That's my problem i hope i explained it well, thanks for help!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,957
    Thanks
    1781
    Awards
    1
    Quote Originally Posted by goroner View Post
    i had to find the total number of graphs given the labels for all the vertices (graphs with edges starting from 1 till complete graph), actually the formula was given i needed to prove it, the formula is this : 2^(n(n-1)/2) if V(G) = n, so to prove this i used math. induction
    There is absolutely no need to use induction.
    If you have n labeled vertices, then any two of the them determine an edge. Any subset of edges determine a simple graph.

    There are \binom{n}{2}=\frac{n(n-1)}{2} pairs of vertices. So there are that number of possible edges.

    Thus there are \displaystyle 2^{\frac{n(n-1)}{2}} subsets of edges. That many possible graphs on n labeled vertices.
    Last edited by Plato; May 28th 2011 at 03:59 PM. Reason: Correct typo
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jun 2010
    From
    Skopje
    Posts
    54
    hmm, you wrote 2^(n(n-2)/2) , the formula says: 2^(n(n-1)/2) ?? , anyway the induction is quite aint it?, and the problem here is not really that part but how many graphs from those 2^(n(n-1)/2) there is that contain m edges exactly?? i dont know how to find that , read my post again if you can it's somewhere in the middle that i explain for the second problem in the task, thanks for replay tough =)

    edit: ye got your idea, about the boolean of set it's quite ideal but i don't know what in the formula says n-1 instead of the n-2 you wrote..
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,957
    Thanks
    1781
    Awards
    1
    That was a typo. It has been corrected.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jun 2010
    From
    Skopje
    Posts
    54
    damn it, i didnt even tried to solve the (n 2) to see that you wrote it wrong =B, thanks for edit it's clear now, but what about the part two which is the critical..
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,957
    Thanks
    1781
    Awards
    1
    Quote Originally Posted by goroner View Post
    but what about the part two which is the critical..
    What part two?
    I do not see a part two.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Jun 2010
    From
    Skopje
    Posts
    54
    well this is it ill explain it here again: so having the formula to find all the graphs with the particular labeling that is 2^(n(n-1)/2) now it is asked to find the subset (the number) of graphs that have exactly m edges.. , as i wrote this i kinda get idea that i can use something like combinations (n m) and plug that in the boolean determination that is 2^(n m) , but the problem is that as i explained top, i might have incident edges so there might be 2 edges determined by 3 vertices cause those edges are incident.. etc..

    something like: 2^(n!/(m!(n-m)!)
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,957
    Thanks
    1781
    Awards
    1
    Quote Originally Posted by goroner View Post
    to find the number of graphs that have exactly m edges.. ,
    O.K. I will play the 'back-of-the-book' game.
    The game goes goes like this.
    The answer is: \binom{\frac{n(n-1)}{2}}{m}.
    You are required to explain why that is the answer.
    Be careful to explain the limits on m.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Jun 2010
    From
    Skopje
    Posts
    54
    ill think about it now i go in bed , i got some ideas tough , and many thanks ill give explanation as soon as i got one xD
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Junior Member
    Joined
    Jun 2010
    From
    Skopje
    Posts
    54
    well i guess this is how it goes: (n(n-1)/2 m) just because firstly you get all the possible ways to construct edge between 2 vertices then from all those you pick m to construct the actual graph with m edges, since the n(n-1)/2 ways might have those edges scattered around the n vertices the combinations m of n(n-1)/2 will include all possible ways to get those m edges, i.e. incident and non-incident edges are included... as i imagine it comes this way: you get m separate graphs that include one edge each and those graphs are different i mean all the edges are unique so after that you combine them into one larger graph which is the graph with m edges, you do this for all the possible layouts of per edge graphs, so you take the next m graphs with unique single edge and combine and again get big graph with m edges and so on for all the possible ways which is the number of this kind of sampling if can be said that way.., that's my explanation might not be mathematical but i don't know if there is some mathematical formal explanation.. Thanks! =)
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,957
    Thanks
    1781
    Awards
    1
    You are grossly over-thinking the question.
    The question simply asks: "How many labeled graphs on n vertices have exactly m edges?"

    ANY set of m edges is such a graph.
    The number of those sets is \binom{\frac{n(n-1)}{2}}{m}.
    Note that 0\le m\le \frac{n(n-1)}{2}.

    That is the complete answer.
    Last edited by Plato; May 29th 2011 at 06:05 AM.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Junior Member
    Joined
    Jun 2010
    From
    Skopje
    Posts
    54
    well yes that is what i said but a bit more writing i did, i just explained how i imagined it ( sorry but i'm not good at proving im still learning.. ) =)
    and btw since the graphs must be simple i think 0 <= m <= n/2 am i right?
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,957
    Thanks
    1781
    Awards
    1
    Quote Originally Posted by goroner View Post
    since the graphs must be simple i think 0 <= m <= n/2 am i right?
    No indeed. A complete graph on n vertices has \frac{n(n-1)}{2} edges. It is a simple graph.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Junior Member
    Joined
    Jun 2010
    From
    Skopje
    Posts
    54
    ahh ye n(n-1)/2 is complete = > simple , thanks for all the replays you really helped me =)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Labeling a cube
    Posted in the Calculus Forum
    Replies: 0
    Last Post: December 11th 2011, 08:10 PM
  2. Graph problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 1st 2009, 01:48 PM
  3. Labeling Equations
    Posted in the LaTeX Help Forum
    Replies: 2
    Last Post: May 7th 2009, 03:26 PM
  4. graph of problem
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: December 12th 2008, 10:49 AM
  5. Please help ! Graph problem
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 18th 2008, 08:11 AM

Search Tags


/mathhelpforum @mathhelpforum