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!