Partitions of Graphs VII: The Cases of 5 and 7

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)