This is the seventh in a series, the first being here: Part I, the previous here: Part VI.

In the previous post I defined a Q1 graph to be a graph G with q(G)=1. We found examples of Q1 graphs for every n between 2 and 10 except 5 and 7.

Let’s talk about the case n=1. There is only one graph with a single node. Here is a picture of it

o

Obviously p(o)=1 and q(o)=p(1)-p(o)=1-1=0, so there are no Q1 graphs for n=1. Let’s make the following:

**Definition:** If **P** is a partition prohibited by a Q1 graph, we will call **P** a Q1 partition.

Now for the case n=5.

**Theorem 1:** There are no Q1 graphs with five nodes.

*Proof:* Here are the partitions of 5:

**5**

**4+1**

**3+2**

**3+1+1**

**2+2+1**

**2+1+1+1**

**1+1+1+1+1**

We will eliminate each of these in turn as possible partitions prohibited by a Q1 graph. In my previous post we saw that **5** cannot be prohibited by a Q1 graph. Let’s state that as a lemma. Refer to the previous post for a proof.

**Lemma 0:** Any Q1 graph with n>2 nodes is connected. In other words, **n** is not a Q1 partition.

Also, since **1+1+1+1+1** is allowed by every (five node) graph it cannot be a Q1 partition. In fact we can extend this result.

**Lemma 1:** Any partition that has a 1 as a summand is not Q1 (call such a partition a type 1 partition).

The idea behind the proof of Lemma 1 is that any connected graph, say with k nodes, has at least one node that can be cut off by snipping some edges without disconnecting the rest of the graph, to give a connected graph on k-1 nodes (plus a solitary disconnected node).

Lemmas 0 and 1 eliminate all partitions but **3+2** as possibilities for Q1 partitions. We take care of that with:

**Lemma 2:** Any partition of the form (**m+k**)**+m+ . . . +m+k+. . .+k** (let’s call this a type 2 partition, since it appears in lemma 2) is not Q1. In other words any partition with summands consisting of a bunch of k, a bunch of m and a single m+k is not Q1.

*Proof of Lemma 2:* Given a Q1 graph G, it is connected, by Lemma 0. Next, assuming a type 2 partition **P**: (**m+k**)**+m+ . . . +m+k+. . .+k **is prohibited by G, the partition (**m****+m+ . . . +m+k+k+. . .+k** must be allowed by G. But since G is connected at least one of the size m subgraphs must be connected via an edge to at least one of the size k subgraphs. Color the nodes in these two subgraphs the same color to obtain a good coloring of G corresponding to **P**. Therefore **P** is not prohibited, a contradiction. Therefore **P** is not Q1. *end of proof of Lemma 2.*

**3+2** is a type 2 partition, therefore it is not Q1. Since there are no partitions of 5 that are Q1, there are no 5-node Q1 graphs. This concludes the proof of Theorem 1.

**Theorem 2:** There are no 7-node Q1 graphs.

*Proof:* Here are the partitions of 7:

**7**

**6+1**

**5+2**

**5+1+1**

**4+3**

**4+2+1**

**4+1+1+1**

**3+3+1**

**3+2+2**

**3+2+1+1**

**3+1+1+1+1**

**2+2+2+1**

**2+2+1+1+1**

**2+1+1+1+1+1**

**1+1+1+1+1+1+1**

Eliminating the type 1 partitions and the partition 7 we have left:

**5+2**

**4+3**

**3+2+2**

These are all type 2 partitions:

**5+2 = (3+2)+2
**

**4+3 = (3+1)+3
**

**3+2+2 = (2+1)+2+2
**

*End of proof of Theorem 2.*

We have seen that 5 and 7 do not permit Q1 graphs, but 9 does. In fact the reason 9 does is that it is divisible by 3. One might be tempted to guess that prime numbers do not admit Q1 graphs (with 2 and 3 being flukes). Of course the next number to test this guess on is 11. The case of n=11 will be the subject of my next post.

Part VIII: The Case of 11 (and 17)

Pingback: Partitions of Graphs VIII: The case of 11 (and 17) « MATH with my KIDS