I’ve been sick and had to stay home from work the last several days. This morning I told my kids that they could choose to put away their clothes or do math. They chose math. I set both B and A working on different problems in our partitions of graphs research project. B had previously shown that 2+2 is a Q1 partition with the claw being it’s Q1 graph. I asked him to decide whether any of the other partitions of 4:
could be Q1. He started with 1+1+1+1. He said this partition you can always make with any 4-vertex graph, so it is not Q1. Next he tackled 2+1+1. He gave me an algorithm to make this partition from any (connected [all of our graphs start out connected so far. I think next time I might introduce the idea of a graph not being connected and still being considered one graph]) 4-vertex graph. Here is the algorithm: choose two adjacent vertices. Do not cut the edge between them, but cut all other edges in the graph. This gives the partition 2+1+1. Next he dealt with the partition 4. If the graph is connected, then of course 4 is a partition you can make trivially (again we’ll have to come back to this once we talk about starting with disconnected graphs). 3+1 he doesn’t believe can be Q1. He thinks that it may also be a partition allowed by any connected 4-vertex graph. He is going to think about why, and we’ll return to it at our next session.
A had started analyzing what she called the ice cream cone. I had her redraw it for me today. I think that it had more vertices before, but today it ended up being a 4-cycle (the square). We checked one by one that you can make any partition of 4 with this graph. Next I had her think about the 5-cycle, then 6 and 7 and finally 8. After doing 7 she was pretty sure that you can always make all partitions of n with an n-cycle. She hasn’t given me any justification, but I think she sees what’s going on. Next session I think I will have her think about what partitions can be made with stars.