Partitions of Graphs VIII: The case of 11 (and 17)

This is the eighth in a series, the first being here: Part I and the previous here: Part 7.

We have shown that there are no Q1 graphs with n=5 nodes or with n=7 nodes.  Also, in the case of n=9, it apears that the reason there are Q1 graphs is that 9 is divisible by 3 (3+3+3 being the Q1 partition).  It is tempting to guess that for n=11 there are no Q1 graphs.  This however is not the case.  Here is one

```                o
|
o-o-o-o-o-o-o-o-o
|
o```

The prohibited partition is 4+4+3.  The easiest way to see this is to show that any partition which has a 1, 2, or anything larger than a 4 as a summand is allowed, so the only prohibited partitions have only 4s and 3s as summands.  But there is only one way to represent 11 as a sum of 4s and 3s, namely 4+4+3.  The same logic works to show that this 17 node graph is also Q1:

```                            o
|
o-o-o-o-o-o-o-o-o-o-o-o-o-o-o
|
o```

But adding another six nodes to the tail gives this graph which is not Q1:

```                                        o
|
o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o
|
o```

Since there are two ways of representing 23 as a sum of 4s and 3s, namely 4+4+4+4+4+3 and 4+4+3+3+3+3+3.