Labeled graphs of graphs up to isomorphism? (I think the second one...)

labeled and also simple graphs.

can anybody post answer (i mean just the number)

A001349 in the OEIS is connected graphs up to isomorphism. Probably you can figure out how to find connected labeled graphs on your own.

i think you could complet the graph to a complete one and then color the edges red if the exist initialy and blue if the didn't exist initaly , and then count the pemutations...

oh its not so hard the number of graph that are connected with 6 vertices is the number of graph with 6 vertices $-$the graph that are not connected!! and the graph that are not connected with $6$vertices can find with Recursive:)

...from the booklet Turkish Mathematical Olmypiad 2006: Problem: An airline company is planning to run two-way flights between some of the six cities $A$, $B$, $C$, $D$, $E$ and $F$. Determine the number of ways these flights can be arranged so that it is possible to travel between any two of these six cities using only the flights of this company. Solution: Using the inclusion-exclusion principle we find that the number of ways the flights can be arranged so that each city is connected to at least one other city by a flight is \[2^{\binom 62} - \binom 61 2^{\binom 52} +\binom 62 2^{\binom 42} - \binom 63 2^{\binom 32} + \binom 64 2^{\binom 22} - \binom 65 + \binom 66 = 27449\] Among these, the configurations that do not satisfy the condition of the problem, and the corresponding number of ways the flights can be arranged are shown in the following figure: [asy][asy] unitsize(30); pair A, B,C,D,E,F; real x, y; A=(0,0); B=(2,1); C=(2.5, 0.8); D=(2.3, -1); E=(1.9, -1.1); F=(0, -0.4); draw(A--B); draw(C--D); draw(E--F); dot(A);dot(B);dot(C);dot(D);dot(E);dot(F); label("$\frac{6!}{2^3 3!}$", (3, 0)); x=5; A=(x+0,0); B=(x+0.2,1); C=(x+1.5, 0.8); D=(x+1.6, 0.3); E=(x+1.5, -1.1); F=(x+0, -0.4); draw(A--B--C--cycle); draw(D--E--F--cycle); dot(A);dot(B);dot(C);dot(D);dot(E);dot(F); label("$\frac{1}{2}{{6} \choose {3}}$", (x+2.5, 0)); x=10; A=(x+0,0); B=(x+0.2,1); C=(x+1.5, 0.8); D=(x+1.6, 0.3); E=(x+1.5, -1.1); F=(x+0, -0.4); draw(A--B--C--cycle); draw(D--E--F); dot(A);dot(B);dot(C);dot(D);dot(E);dot(F); label("$3 \cdot {{6} \choose {3}}$", (x+2.5, 0)); x=0; y=-4; A=(x+0,y+0); B=(x+0.2,y+1); C=(x+1.5, y+0.8); D=(x+1.6, y+0.3); E=(x+1.5, y+-1.1); F=(x+0, y+-0.4); draw(A--B--C); draw(D--E--F); dot(A);dot(B);dot(C);dot(D);dot(E);dot(F); label("$\frac{3 \cdot 3}{2} {{6} \choose {3}}$", (x+2.5, y+0)); x=5; y=-4; A=(x+0,y+0); B=(x+1.7,y+1); C=(x+2.0, y+0.8); D=(x+1.8, y+-1); E=(x+0.6, y+-1.1); F=(x+0, y+-0.4); draw(A--B); draw(C--D--E--F--cycle); draw(C--E);draw(F--D); dot(A);dot(B);dot(C);dot(D);dot(E);dot(F); label("${{6} \choose {2}}$", (x+2.5, y+0)); x=10; y=-4; A=(x+0,y+0); B=(x+1.7,y+1); C=(x+2.0, y+0.8); D=(x+1.8, y+-1); E=(x+0.6, y+-1.1); F=(x+0, y+-0.4); draw(A--B); draw(C--D--E--F--cycle); draw(C--E); dot(A);dot(B);dot(C);dot(D);dot(E);dot(F); label("${{6} \choose {2}}{{4} \choose {2}}$", (x+2.5, y+0)); x=0; y=-8; A=(x+0,y+0); B=(x+1.7,y+1); C=(x+2.0, y+0.8); D=(x+1.8, y+-1); E=(x+0.6, y+-1.1); F=(x+0, y+-0.4); draw(A--B); draw(C--D--E--F--cycle); dot(A);dot(B);dot(C);dot(D);dot(E);dot(F); label("$3\cdot {{6} \choose {2}}$", (x+2.5, y+0)); x=5; y=-8; A=(x+0,y+0); B=(x+1.7,y+1); C=(x+1.8, y+0.8); D=(x+1.5, y+-1); E=(x+1.6, y+-1.8); F=(x+0, y+-0.4); draw(A--B); draw(C--D--F--cycle); draw(E--D); dot(A);dot(B);dot(C);dot(D);dot(E);dot(F); label("$4 \cdot 3 \cdot {{6} \choose {2}}$", (x+2.5, y+0)); x=10; y=-8; A=(x+0,y+0); B=(x+1.7,y+1); C=(x+1.8, y+0.8); D=(x+1.5, y+-1); E=(x+1.6, y+-1.8); F=(x+0, y+-0.4); draw(A--B); draw(C--D--F); draw(E--D); dot(A);dot(B);dot(C);dot(D);dot(E);dot(F); label("$4 \cdot {{6} \choose {2}}$", (x+2.5, y+0)); x=0; y=-12; A=(x+0,y+0); B=(x+1.7,y+1); C=(x+2.0, y+0.8); D=(x+1.8, y+-1); E=(x+0.6, y+-1.1); F=(x+0, y+-0.4); draw(A--B); draw(E--F--C--D); dot(A);dot(B);dot(C);dot(D);dot(E);dot(F); label("$\frac {4!}{2} {{6} \choose {2}}$", (x+2.5, y+0)); [/asy][/asy] Therefore, the answer is $27449 - 745 = 26704$

An involved solution, I think, is good to pair up with the booklet answer above, Note that, the preamble requires, isomorphic graphs are counted multiple times, {\em e.g.}, consider two graphs, with two edges; where, the first is, $(A-B,A-C)$; and, the second is, $(D-E,D-F)$. While these two graphs are isomorphic, they must be counted differently, due to the presence of labels. Our strategy, is to count, through the cardinality of the largest connected subgraph. Let, $M_i$, be the total number of graphs on $6$-vertices, whose maximal connected subset, consists of $i$-vertices (for instance, a graph in $M_3$, must contain a triangle; while any subset with $4$, $5$, or $6$ vertices, must be unconnected). Also note that, $M_0=1$ (simply, a graph with no edges), and $M_1=0$ (if there is an edge, then, at the very least, we can find $2$ connected vertices). Note that, there are, a total of, $2^{\binom{6}{2}}=32768$ graphs, that can be constructed on, $6$-vertices. Hence, the answer we seek is, $32768 - \sum_{i=2}^5 |M_i|-1$. $a)$ $|M_2|:$ Suppose that, the maximal connected subset, consists of $3$-vertices, only. Therefore, the possibilities are, $2+2+2$, $2+2+1+1$; and $2+1+1+1$ (think of these summations, as, partitioning $6$-vertices into equivalence classes, depending on the connectivity). $\bullet$ $2+2+2$ gives us, the following graph, and isomorphisms, $(A-B,C-D,E-F)$, hence, a total of, $$ \frac{\binom{6}{2}\binom{4}{2}\binom{2}{2}}{3!}=15. $$$\bullet$ $2+2+1+1$ gives us, $(A-B,C-D)$, and isomorph graphs (namely, graphs with two edges, where, each edge, has different endpoints). Therefore, the total is, $$ \frac{\binom{6}{2}\binom{4}{2}}{2}=45. $$$\bullet$ Finally, $2+1+1+1+1$ gives us a graph with only one edge, namely, there are, $\binom{6}{2}=15$ such graphs, on $6$-vertices. Hence, $|M_2|=75$. $b)$ Next, we continue by $|M_3|$. The possibilities are, $3+3$, $3+2+1$, and $3+1+1+1$. Also, as a quick exercise, let us count, the total number of connected graphs, on $3$-vertices, where, the vertices are fixed. We can either have a triangle, or, $V$-shapes, and there are, $3$ $V$-shaped structure. Hence, fixing $3$-vertices, gives us, $4$ connected graphs (notice that, the total number of graphs, on $3$-vertices, is, $2^{\binom{3}{2}}=8$. $\bullet$ $3+3$ can be obtained, either, through, $(T,T)$, $(T,V)$, or $(V,V)$; where, $T$ is a triangle, and $V$ is a $V$-shaped structure. There are, $\displaystyle\frac{\binom{6}{3}}{2!}=10$ $(T,T)$-configurations; $\displaystyle\binom{6}{3}\cdot 3 =60$, $(T,V)$-configurations; and finally, $\displaystyle\frac{\binom{6}{3}\cdot 3 \cdot 3}{2}=90$, $(V,V)$-configurations. The total is, $90+60+10=160$ configurations. $\bullet$ $3+2+1$ can be obtained in, a total of, $$ \binom{6}{3}\cdot 4 \cdot \binom{3}{2} = 240, $$diferent ways; where, we first select, three vertices, that will be connected, and count $4$ valid arrangements; and then, select $2$ more vertices, among the remaining $3$. $\bullet$ Finally, $3+1+1+1$ can be obtained in, $\binom{6}{3}\cdot 4 =80$ different way. Thus, $|M_3|=480$. $c)$ $|M_4|$ is a little bit more involved. Let us first, begin by, a fact, that will be very useful in the remaining. Lemma: On $4$-vertices, there are, $38$ connected graphs. Proof: Argue via the total number of edges. Notice that, any graph, on $4$-vertices, with $4$ or more edges, is connected, giving us, $\displaystyle\binom{6}{4}+\binom{6}{5}+\binom{6}{6}=22$. Furthermore, there are configurations on three edges, that are, also, connected; and these are simply, the shapes, without any triangles. Hence, a total of, $\binom{6}{3}-\binom{4}{3}=16$; where, $\binom{6}{3}$ is number of different ways, in which, we can select $3$-edges, out of $6$; and the subtraction, is to eliminate the triangles. Therefore, the answer is, as desired, 38. With the lemma in our hands, now, there are two candidate arrangements, $4+2$, and $4+1+1$; and therefore, the answer is, $$ |M_4|=\binom{6}{4}\cdot 38 \cdot 2 = 1140, $$where, four connected vertices, can be selected in $\binom{6}{4}$ different ways; having selected those $4$ vertices, there are $38$ arrangements; and finally, we have, either, the remaining $2$ connected; or disconnected, thus, a multiplication by $2$. $d)$ $|M_5|$ is hard to work with, directly. Hence, we instead, take a convoluted approach, and begin by, computing the total number of connected graphs, on $5$-vertices. First, note that, there are, a total of, $2^{\binom{5}{2}}=1024$ graphs, that live on $5$-vertices. Among these; $\bullet$ the ones, where the maximal connected subset, has a size $4$, are, $\displaystyle\binom{5}{4}\cdot 38=190$, $\bullet$ the ones, with a maximal connected subset of size $3$, are, $\displaystyle\binom{5}{3}\cdot 4 \cdot 2 =80$, where, the multiplication by $2$, is to take care of, $3+2$, or $3+1+1$; \item and finally, the ones, with a maximal connected subset of size $2$, are, $\displaystyle \frac{\binom{5}{2}\binom{3}{2}}{2}+\binom{5}{2}=25$, where the first, takes care of, $2+2+1$, and the second, for, $2+1+1+1$. Thus, the total number of connected graphs, that can be constructed on $5$-vertices, are, $$ 1024-190-80-25-1=728, $$where, the last item, is to take care of a graph, without any edges. With this, we can now, clinch $|M_5|$ via, $$ \binom{6}{5}\cdot 728 = 4368. $$ $e)$ Now, we will finish up the answer, \begin{align*} |M_6| &= 2^{\binom{6}{2}} - |M_5|-|M_4|-|M_3|-|M_2|-1\\ &=32768 - 4368 - 1140 - 480 - 75 - 1 \\ &=26704. \end{align*}

That was a 3 year revival btw

Math-Ninja wrote: That was a 3 year revival btw Post necessary stuff, don't spam. There is no rule preventing you from posting, if you think you have a detailed/different approach.