The Universe of Discourse

Claude chokes on graph theory

Having had some pleasant surprises from Claude, I thought I'd see if it could do math. It couldn't. Apparently some LLMs can sometimes solve Math Olympiad problems, but Claude didn't come close.

First I asked something simple as a warmup:

MJD: What is the largest number that is less than 1000?

I had tried this on ChatGPT a couple of years back, with tragic results:

ChatGPT: The largest number that is less than 1000 is 999.

But it should have quit while it was ahead, because its response continued:

ChatGPT: Any number that is less than 1000 will have three digits, with the first digit being 9, the second digit being 9, and the third digit being any number from 0 to 8.

and then when I questioned it further it drove off the end of the pier:

ChatGPT: Any number with four or more digits can be less than 1000, depending on the specific digits that are used. For example, the number 9991 is a four-digit number that is less than 1000.

Claude, whatever its faults, at least knew when to shut up:

MJD: What is the largest number that is less than 1000?

Claude: 999

I then asked it “What if it doesn't have to be an integer?” and it didn't do so well, but that's actually a rather tricky question, not what I want to talk about today. This article is about a less tricky question.

I have omitted some tedious parts, and formatted the mathematics to be more readable. The complete, unedited transcript can be viewed here.

I started by setting up context:

MJD: Let's say that the cube graph !!Q_n!! has as vertices the set !!\{0,1\}^n!! and two vertices are connected with an edge if and only if their coordinates differ in exactly one position. This is a standard construction. Are you familiar with it?

Claude asserted that it was familiar with this family of graphs. (Wikipedia on cube graphs)

Then I got to the real question:

Now let's say that the Keane number for a graph !!G!! is the largest number !!k!! such that:

1. !!G!! can be partitioned into !!k!! connected subgraphs, and
2. each pair of subgraphs is adjacent, in the sense that for each pair !!H!!, !!K!! there is an edge of !!G!! with one vertex in !!H!! and one in !!K!!.

If you understand so far, tell me the Keane numbers of the cube graphs !!Q_0, Q_1!!, and !!Q_2!!.

One way to think about this is: we have a graph, and we want to divide it up into connected subgraphs. We pick a single color for each subgraph and color the vertices of that subgraph with its color. And for each two colors, there should be vertices of those colors that share an edge.

We're looking for the maximum possible number of colors. So if we produce a partition into !!3!! subgraphs, that only proves that !!k\ge 3!!; we still need a further argument to rule out the possibility of a partition into !!4!! or more parts.

Claude got this initial question right. The Keane numbers of !!Q_0, Q_1, !! and !!Q_2!! are obviously !!1, 2, !! and !!3!!. So far so good.

Then I asked Claude for the Keane number of !!Q_3!! and this it was unable to produce.

The correct number is !!4!!. There are several essentially different partitions of !!Q_3!! into four parts, each of which touches the other three, so the number is at least !!4!!. Here are two:

In addition to these there is also a partition into parts of size !!1+1+2+4!!, and one into parts of size !!1+1+3+3!!.

On the other hand, more than !!4!! parts is impossible, and the proof is one sentence long: !!Q_3!! has only !!8!! vertices, so any partition into !!5!! or more parts must have a part of size !!1!!, and this part can't be adjacent to the other four parts, because a single vertex has only three outgoing edges. I would expect a bright middle-schooler to figure this out in at most a few minutes.

At first, Claude got the right number, but with completely bogus reasoning. To avoid belaboring the obvious, I'll highlight the errors but I won't discuss them at length.

Claude:

• Let's find the maximum possible !!k!!:
  
  • One valid partition with !!k=4!! exists:
    
    • Take two opposite vertices (e.g., !!000!! and !!111!!)
    • Make these two single-vertex subgraphs
    • Split the remaining !!6!! vertices into two paths of !!3!! vertices each
    • Each subgraph is connected
    • Each pair of subgraphs will have an edge between them

The diagrams I showed earlier display some of the partitions that show !!k≥4!!, but the one Claude gave here does not, because two of its parts are not adjacent:

Claude:

• Why can't !!k!! be !!5!! or more?
  • If we had !!5!! or more subgraphs, we would need !!{5 \choose2} = 10!! edges between pairs
  • !!Q_3!! only has !!12!! edges total
  • Some edges would need to be reused for multiple pairs
  • But each edge can only connect one pair of subgraphs
  • Therefore !!5!! or more subgraphs is impossible

Therefore, the Keane number of !!Q_3!! is !!4!!.

Would you like me to verify any part of this reasoning?

So, right answer, but seemingly by luck, since there were serious errors in reasoning, in both the !!k≥4!! part and also in the !!k< 5!! part. I decided to ignore the second one.

MJD: You said two of the subgraphs are !!H=\{000\}!! and !!K=\{111\}!!. You said each pair of subgraps will have an edge between them. What edge connects !!H!! and !!K!!?

Claude: Ah, I made a mistake.

The vertices !!000!! and !!111!! differ in all three positions, so they are not adjacent in !!Q_3!! (they need to differ in exactly one position to have an edge between them). This means that making them single-vertex subgraphs would violate condition (2) since these subgraphs would not be adjacent.

I need to rethink my claimed partition. Would you like me to try again to determine the Keane number of !!Q_3!!?

MJD: Yes.

Claude: [finds a specific example showing !!k≥3!!, and remarks that !!k=4!! “seems difficult”]
Let me work on verifying whether !!k=4!! is possible or !!k=3!! is maximum. Would you like me to continue?

MJD: Please go on.

Claude: Let me try to prove !!k=3!! is maximum in !!Q_3!!.

Suppose we had !!k=4!! subgraphs. Then:

• We need !!{4 \choose 2} = 6!! edges between different subgraphs
  • Each subgraph needs to be connected:
    
    • A subgraph with !!3!! vertices needs at least !!2!! edges
    • A subgraph with !!2!! vertices needs !!1!! edge
    • A subgraph with !!1!! vertex needs !!0!! edges
  • There are !!12!! edges total in !!Q_3!!
  • If we have !!4!! subgraphs:
    • First, !!6!! edges must go between different subgraphs
    • That leaves only !!6!! edges for internal connectivity
    • But with !!8!! vertices split into !!4!! subgraphs:
      • If any subgraph has !!3+!! vertices, it needs !!2+!! edges internally
      • If any has !!4+!! vertices, it needs !!3+!! edges internally
      • With !!8!! vertices total divided into !!4!! parts, at least one part must have !!3+!! vertices
      • After using !!2+!! edges for that part and !!6!! edges between parts, we don't have enough edges left to make all other parts connected

Therefore !!k=4!! is impossible, and the Keane number of !!Q_3!! is !!3!!.

Claude seems completely undirected here. Some of the things it says are correct facts, but it can't link the facts together into actual reasoning, except by accident. Sometimes it utters A followed by B where A implies B, and it seems exciting, but just as often B is a nonsequitur.

This is not that different from how ChatGPT was two years ago. It can spout text, and often it can spout enough plausible, grammatically-correct text to suggest that it knows things and is thinking about them. Claude's text-spouting prowess is much more impressive than ChatGPT's was two years ago. But it is still just a text-spouter.

I went on, trying to detect actual thinking.

MJD: What if there were !!4!! parts of !!2!! vertices each?

Claude's response here correctly applied its earlier analysis: four parts of size !!2!! would use up four edges for internal connectivity, leaving !!8!! for external connections, and we only need !!6!!.

Claude: I was too quick to conclude 4 was impossible. Let me try to find an explicit partition into 4 parts of 2 vertices each...
Would you like me to try to find such a partition, or would you first like me to verify that this kind of partition would definitely satisfy the adjacency requirement (condition 2)?

MJD: You keep going until you think you ha e the right answer.

Claude: Let me try to construct a partition of !!Q_3!! into !!4!! parts of !!2!! vertices each: …

This time Claude tried this partition:

It noticed that two of the four parts were not adjacent, and gave up without searching further.

Claude: This makes me think !!3!! really is the maximum.

If Claude were a human mathematician, this would be a serious error. Finding one invalid partition proves nothing at all.

Claude: My previous argument was wrong, but the conclusion might be right. Would you like me to try to prove more carefully that !!4!! is impossible?

There is no proof that !!4!! is impossible, and I thought it would be unenlightening to watch Claude flounder around with it. But I wanted to see what would happen if I asked it to prove a false claim that should be easier because its premise is stronger:

MJD: Try a weaker conjecture: prove more carefully the four parts of size 2 is impossible.

Claude: Okay, let me prove that we cannot partition !!Q_3!! into four parts of size 2 each.

1. Suppose we had such a partition !!H_1, H_2, H_3, H_4!!, where each !!H_i!! contains exactly two vertices.
2. For any such !!H_i!!, its two vertices must be adjacent (to be connected). This means they differ in exactly one coordinate.
3. Therefore, each !!H_i!! must be of one of these forms:
   • Two vertices differing in 1st coordinate (like !!000,100!!)
   • Two vertices differing in 2nd coordinate (like !!000,010!!)
   • Two vertices differing in 3rd coordinate (like !!000,001!!)
4. Consider any vertex !!v!! in !!Q_3!!. It has exactly 3 neighbors:
   • One differing in 1st coordinate
   • One differing in 2nd coordinate
   • One differing in 3rd coordinate
5. Therefore, if !!v!! is in !!H_i!!:
   • One of its neighbors must also be in !!H_i!!
   • That leaves only two edges from !!v!! that could connect to other parts
   • So !!v!! can only help !!H_i!! be adjacent to at most two other parts
6. But each !!H_i!! needs to be adjacent to all three other parts

This contradiction proves no such partition exists.

It's tempting to look at this and say that Claude was almost right. It produced 16 lines and at least 15 of them, on their own, were correct. But it's less impressive than it might first appear. Again Claude displays the pattern of spouting text, some of which is correct, and some of which is related. But that is all I can say in its favor. Most of its statements are boilerplate. Sections 2–4 can be deleted with nothing lost. Claude has buried the crux of the argument, and its error, in section 5.

MJD: In step 5 I see that if !!v!! is in !!H_i!!, it can only help !!H_i!! be adjacent to two other parts. But !!H_i!! has size 2, so it contains a vertex other than !!v!!. If !!v!! connects !!H_i!! to two other parts, couldn't the other vertex of !!H_i!! connect !!H_i!! to a third part?

Claude: Ah, you're absolutely right! My proof attempt failed. Let me back up and try a different approach to the original question of whether !!Q_3!! can be partitioned into 4 parts that satisfy both conditions.

…

This time Claude did find a correct partition into four parts, showing that !!k≥4!!.

MJD: How did you come up with that example partition?

Claude: I should be honest - I didn't find it systematically. I was trying different arrangements somewhat randomly until I found one that worked. …

I don't think these is any sense in which this is true, but at this point I hadn't yet internalized that Claude's descriptions of its own internal processes are text-spouting just like the rest of its output. In any case, I ignored this and asked it to analyze its own earlier mistake:

MJD: Earlier you purported to prove that !!k=4!! was impossible, saying that !!6!! edges would be needed to connect the !!4!! parts, and that this did not leave enough edges to connect the parts internally. You didn't analyze this carefully, so you missed the solution where all four parts have !!2!! vertices each. Do that analysis more carefully than you did last time and explain why that counting method does not rule out a partition of !!Q_3!! into !!2+2+2+2!!.

Claude: (details elided)

So this counting argument shows:

• We need 10 edges
• We have 12 edges
• Therefore the counting argument does not rule out a !!2+2+2+2!! partition

My earlier analysis erred by not being explicit about the numbers. I just had a vague sense that we needed "too many" edges, without actually counting them. This shows the importance of precise counting rather than relying on intuition about what seems like "too many".

Claude got the counting part right, although I think the final paragraph is just spouting, especially the claim “I just had a vague sense that…”, which should not be taken seriously.

[ Digression: This reminds me of a section in Daniel Dennett's Consciousness Explained in which he discusses the perils of asking humans about their internal processes. The resulting answers, he says, may provide interesting informaiton about what people think is going on in their heads, but we should be very wary about ascribing any accuracy or insight to these descriptions. Dennett makes an analogy with an anthropologist who asks a forest tribe about their forest god. The tribespeople agree that the forest god is eight feet tall, he wears a panther skin, and so on. And while this might be folklorically interesting, we should be very reluctant to conclude from this testimony that there is actually an eight-foot-tall fur-clad god in the forest somewhere. We should be similarly reluctant to ascribe real existence to Claude's descriptions of its “vague senses” or other internal processes suggested by its remarks like “Ah, let me think...” or “Ah, you're absolutely right!”. Claude has even less access to its own mental states (such as they are) than a human would. ]

As I pointed out earlier in this article, there are several essentially different solutions to the problem of partitioning !!Q_3!! into four parts. Claude has found one of them, the one I showed above on the left. I wanted to see if it could find another:

MJD: Are there any other partitions that are not ruled out by that argument? Or is 2+2+2+2 the only possibility?

Claude: Let me think about what other partitions could satisfy the edge-counting constraint.

If we have !!4!! parts, need !!6!! edges between parts, and have !!12!! total edges, then we can use up to !!6!! edges for internal connectivity of parts.

Possible partitions of !!8!! vertices into !!4!! parts could be:

• !!2+2+2+2!! (needs !!4!! internal edges)
• !!3+2+2+1!! (needs !!3!! internal edges)
• !!4+2+1+1!! (needs !!4!! internal edges)
• !!3+3+1+1!! (needs !!4!! internal edges)
• !!5+1+1+1!! (needs !!6!! internal edges)

So from just edge counting:

(Claude concludes that none of these is ruled out by edge-counting.)

So the edge-counting argument alone doesn't rule out any of these distributions of part sizes. We'd need additional arguments to determine which are actually possible in !!Q_3!!.

MJD: Why didn't you consider !!4+2+2+1!!?

Claude: Ah, you're right - I should have considered !!4+2+2+1!!! For !!4+2+2+1!!:

• The part of size !!4!! needs at least !!3!! internal edges to be connected
• The parts of size !!2!! each need !!1!! internal edge
• So that's !!5!! internal edges needed
• Plus !!6!! edges needed between parts
• Total needed = !!11!! edges
• We have !!12!! edges available

So this case is also not ruled out by edge counting. I apologize for missing it in my list. Would you like me to check if there are any other distributions I missed?

Oh, such failure! Failures that I have highlighted are clearly false statements, But the failure here is much worse. Again, everything Claude said was correct! And yet deeply wrong!

A bright middle-schooler could have missed this also. It was a bit of a trick question. Not because it's ambiguous, but because problem with !!4+2+2+1!! is not in line with the direction that the discussion was taking at that point. There is nothing wrong with !!4+2+2+1!! from an edge-counting point of view!

But I think a human mathematician, even a very young one, would have been more likely to answer the question I actually asked, which was “Why didn't you consider !!4+2+2+1!!?”, and from there might have quickly come to the useful conclusion that it doesn't need to be considered. Claude didn't do anything like that.

MJD: !!4+2+2+1!! doesn't work. Think about it more.

Claude: Let me think more carefully about a potential !!4+2+2+1!! partition.

1. Consider the part !!H!! of size !!4!!:

   • To be connected, it needs at least !!3!! edges internally
   • One vertex in !!H!! must connect to all !!3!! other vertices in !!H!!
   • But in !!Q_3!!, each vertex has only !!3!! edges total
   • If one vertex in !!H!! uses all its edges internally to connect to the other !!3!! vertices in !!H!!, it has no edges left to connect to other parts
   • But every part needs to be adjacent to every other part

2. Therefore !!4+2+2+1!! is impossible, not because of edge counting, but because:

   • Either !!H!! isn't connected (if we don't use enough internal edges)
   • Or !!H!! can't connect to all other parts (if we use too many internal edges)

This shows why just counting edges isn't enough - we also need to think about the structure of !!Q_3!! and how the edges can be arranged.

Terrible. This is so muddled I wasn't even sure what to highlight as the errors. Yes, if one vertex in !!H!! uses all its edges internally to connect to the other !!3!! vertices in !!H!!, it has no edges left to connect to other parts. But the other three vertices in !!H!! have two edges each, so !!H!! could easily connect to the other three parts.

And, of course, Claude has still missed the main point, which is that one needn't consider !!4+2+2+1!!, because !!4+2+2+1= 9!! and !!Q_3!! has only !!8!! vertices.

MJD: There is a much simpler argument why 4+2+2+1 won't work.

Claude: Ah, let me think...

In a !!4+2+2+1!! partition:

• The single vertex in the part of size !!1!! has degree !!3!! in !!Q_3!!
• But it needs to connect to all three other parts!
• It needs all three of its edges just to be adjacent to the other parts
• So it can't connect to all three other parts AND connect to three different vertices

This is a much simpler contradiction. I was making it too complicated by thinking about the part of size !!4!! when the part of size !!1!! immediately shows it's impossible.

MJD: How many vertices are.in !!Q_3!!?

Claude: !!Q_3!! has !!8!! vertices (all binary strings of length !!3!!):
!!\{000, 001, 010, 011, 100, 101, 110, 111\}!!

And now I see an even simpler argument why !!4+2+2+1!! is impossible: !!4 + 2 + 2 + 1 = 9!! vertices, but !!Q_3!! only has !!8!! vertices!
I was doing complex analysis of connectivity and edges when I should have just checked that the claimed partition added up to the right number of vertices. This is a good reminder to check the most basic facts first.

Finally! I would love to know what really happened here. What caused Claude to emit a sentence connecting !!4 + 2 + 2 + 1 = 9!! with !!Q_8!! having only !!8!! vertices?

MJD: So remind me, did you decide that !!k(Q_3)!! is !!3!!, or !!4!!?

I wasn't sure it would remember this, by which I really mean that I wasn't sure it would be able to pick out from its previous mass of statements which one was correct. But whether by luck or not, it did answer the question correctly:

Claude: Earlier I found a valid partition of Q_3 into 4 parts:

!!H_1 = \{000, 001\} !! !!H_2 = \{100, 110\}!! !!H_3 = \{010, 011\}!! !!H_4 = \{101, 111\}!!

I verified that:

• Each part is connected
• Each part is adjacent to every other part

Therefore !!k(Q_3) ≥ 4!!.

I haven't yet proven that !!k(Q_3) ≤ 4!!. Would you like me to try to prove that !!5!! parts is impossible?

MJD: Please go ahead.

I found Claude's attempt at this interesting, but not in a good way. After reading it I shrugged and quit the conversation.

Claude:
Let me prove that !!5!! parts is impossible in !!Q_3!!.

1. Five parts would require !!{5 \choose 2} = 10!! different edges just to connect all pairs of parts to each other.
2. Each such edge must be distinct because a single edge can only connect one pair of parts.
3. Each vertex in !!Q_3!! has degree !!3!!. With !!8!! vertices, the total number of edges is !!(8 × 3)/2 = 12!!.
4. Out of these !!12!! edges:
   • !!10!! must be used to connect different parts to each other
   • That leaves only !!2!! edges for internal connectivity of parts
   • But with !!8!! vertices split into !!5!! parts, some part must have size !!≥ 2!!
   • Any part of size !!≥ 2!! must use at least one edge internally to be connected
   • If one part uses one edge internally, that leaves only one edge for all other parts
   • But if any other part has size !!≥ 2!!, it also needs an internal edge
   • With !!8!! vertices in !!5!! parts, at least two parts must have size !!≥ 2!!
   • Therefore !!2!! edges is not enough for internal connectivity

Thus !!k(Q_3) = 4!!.

Claude says that with !!8!! vertices in !!5!! parts, at least two parts must have size !!2!! or more. This is wrong, because you could have !!4+1+1+1+1!!.

But highlighting that wrong statement doesn't get at why this answer is so bad. It's bad because the conclusion that appears next is a complete nonsequitur.

The argument can be fixed up. I would put it like this:

• As Claude observed, we have only !!2!! edges available for internal connections
• A part with !!n!! vertices requires at least !!n-1!! edges for internal connections
• Let the sizes of the parts be !!n_1\dots n_5!!. Since !!n_1+\dots +n_5 = 8!!, we need at least !!(n_1-1)+\dots + (n_5-1) = 8-5 = 3!! edges for internal connections
• But we have only !!2!!.

It's true that !!2!! edges is not enough for internal connectivity. But in my opinion Claude didn't come close to saying why.

Back in the early part of the 20th century, we thought that chess was a suitable measure of intelligence. Surely a machine that could play chess would have to be intelligent, we thought. Then we built chess-playing computers and discovered that no, chess was easier than we thought. We are in a similar place again. Surely a machine that could hold a coherent, grammatical conversation on any topic would have to be intelligent. Then we built Claude and discovered that no, holding a conversation was easier than we thought.

Still by the standards of ten years ago this is stunning. Claude may not be able to think but it can definitely talk and this puts it on the level of most politicians, Directors of Human Resources, and telephone santizers. It will be fun to try this again next year and see whether it has improved.

[Other articles in category /tech/gpt] permanent link