2
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ By all complete graphs did you perhaps mean all connected graphs? $\endgroup$ – hardmath Oct 15 '16 at 15:54
  • $\begingroup$ Sorry. Yes, thanks. $\endgroup$ – user36124 Oct 15 '16 at 15:56
  • $\begingroup$ Given your existing work, you may find the earlier Question Why there are 11 non-isomorphic graphs of order 4? a useful reference. These include non-connected possibilities. $\endgroup$ – hardmath Oct 15 '16 at 16:03
  • 1
    $\begingroup$ You need all connected graphs on 4 vertices (6 of them) with two separate vertices and the pair of 3-line/triangle with 3 disconnected vertices, etc. 6 + 2 + 1 + 1 = 10. To put it another way, the number of graphs on N are the sum of the number of connected graphs on N plus the number of connected graphs on N-1 ... 1. $\endgroup$ – gilleain Oct 15 '16 at 16:08
  • $\begingroup$ You may be interested to look at findstat.org/StatisticFinder/Graphs by the FindStat project $\endgroup$ – Alexander Konovalov Oct 15 '16 at 17:05
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.