Depiction of all graphs (not necessarily connected) with 6 vertices I am searching (with no unsuccess) the WWW for a depiction of all non-isomorphic graphs with 6 vertices.
On the site http://www.graphclasses.org/smallgraphs.html I found an incomplete list, but all graphs with 5 vertices (34 ones). According to the integer sequence A000088, there should be 156 of them. A paper by Cvetkovic and Petric http://www.sciencedirect.com/science/article/pii/0012365X84900335 gives all connected graphs with 6 vertices (112 ones).
If I take all connected graphs (112) and take all graphs with 5 vertices adding a separate node (34), then I have 146 graphs. Which 10 graphs are missing?
Thank you very much!
 A: We can partition the graphs by the number of connected components.
One connected component: There are $112$ connected graphs with $6$ vertices
Two connected components: There can be


*

*A connected component of size $1$ and a connected component of size $5$ ($1 \cdot 21 = 21$ possibilities)

*A connected component of size $2$ and a connected component of size $4$ ($\color{red}{1 \cdot 6 = 6}$ possibilities)

*A connected component of size $3$ and another connected component of size $3$ ($\color{red}{3}$ possibilities - $P_3 \sqcup P_3$, $P_3 \sqcup K_3$, or $K_3 \sqcup K_3$)


Three connected components: There can be


*

*Two connected components of size $1$ and a connected component of size $4$ ($1 \cdot 1 \cdot 6=6$ possibilities)

*A connected component of size $1$, one of size $2$, and one of size $3$ ($1 \cdot 1 \cdot 2 = 2$ possibilities)

*Three connected components of size $2$ ($\color{red}{1}$ possibility - $P_3 \sqcup P_2 \sqcup P_2$)


Four connected components: There can be only be three connected components of size $1$ and one of size $3$, for $1 \cdot 1 \cdot 1 \cdot 2 = 2$ possibilities
Five connected components: There can only be four connected components of size $1$ and one of size $2$, for $1 \cdot 1 \cdot 1 \cdot 1 \cdot 2 = 2$ possibilities
Six connected components: One possibility
Add these up and you get $112+21+6+3+6+2+1+2+2+1=156$ graphs.
The ones in red are the ones you are missing - they are not obtained from adding an isolated vertex to a graph with $5$ vertices.
A: Perhaps the easiest way to systematically count is to begin with the integer partitions of six as denoting the sizes of components in your (not necessarily connected) graphs.  There are eleven possibilities.
Some of these give rise to a single (up to isomorphism) graph:
$1 + 1 + 1 + 1 + 1 + 1$
$2 + 1 + 1 + 1 + 1$
$2 + 2 + 1 + 1$
$2 + 2 + 2$
Some give rise to two possibilities each as three nodes can form a connected component in exactly two ways:
$3 + 1 + 1 + 1$
$3 + 2 + 1$
Then there are three possibilities for this partition:
$3 + 3$
because the two components can be non-isomorphic in one way but isomorphic in two ways.
From the earlier Question we see that there are six connected graphs on four vertices, so each of these gives six possibilities:
$4 + 1 + 1$
$4 + 2$
Then we get down to the cases you previously considered:
$5 + 1$ (a connected component of five vertices and one extra node)
$6$ (a connected component of six vertices)
There are respectively $21$ and $112$ of these cases (see OEIS A001349, Number of connected graphs with n nodes).  The previous small cases numbered $23$, and $23+21+112= 156$.
