Thread: 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!

Originally Posted by goroner

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 pairs of vertices. So there are that number of possible edges.

Thus there are subsets of edges. That many possible graphs on n labeled vertices.

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

That was a typo. It has been corrected.

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

Originally Posted by goroner

but what about the part two which is the critical..

What part two?
I do not see a part two.

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

Originally Posted by goroner

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: .
You are required to explain why that is the answer.
Be careful to explain the limits on m.

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

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! =)

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
Note that .

That is the complete answer.

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?

Originally Posted by goroner

since the graphs must be simple i think 0 <= m <= n/2 am i right?

No indeed. A complete graph on n vertices has edges. It is a simple graph.

ahh ye n(n-1)/2 is complete = > simple , thanks for all the replays you really helped me =)