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
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:
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:
Eliminating the type 1 partitions and the partition 7 we have left:
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.