{
  "$type": "site.standard.document",
  "content": "---\ntitle: \"Writing graph theory proofs with ChatGPT\"\ndescription: \"Asking ChatGPT to prove the five colour and four colour theorems with my\n  mathematician father-in-law, and his reaction to the results.\"\ntags:\n  - ai\n  - teaching\n---\n\nPosting logs of [ChatGPT](https://chat.openai.com) interaction is getting a bit\npassé by now in Feb '23, so I'll stop doing it soon (I promise). But yesterday I\nwas hanging out with my father-in-law and showing how it might impact his\nclasses---he's Associate Chair of the Mathematics Department at a top uni in\nChina.\n\nThe prompts were his (with a bit of light suggesting from me), responses from\nChatGPT.\n\n**Write a proof of of Pythagoras's theorem.**\n\nPythagoras's theorem states that in a right triangle, the square of the length\nof the hypotenuse (the side opposite the right angle) is equal to the sum of the\nsquares of the lengths of the other two sides. Symbolically, this can be written\nas:\n\nc^2 = a^2 + b^2\n\nwhere c is the length of the hypotenuse, and a and b are the lengths of the\nother two sides.\n\nProof:\n\nDraw a right triangle ABC with sides AB (a), BC (b), and AC (c).\n\nDraw squares with sides AB, BC, and AC on each side of the triangle, as shown\nbelow:\n\n[Diagram of a right triangle with squares on each side]\n\nThe area of each of the squares is equal to the square of the length of its\nside. Hence:\n\na^2 = AB x AB = area of square with side AB\n\nb^2 = BC x BC = area of square with side BC\n\nc^2 = AC x AC = area of square with side AC\n\nConsider the combined area of the squares on the two smaller sides (a and b). It\ncan also be obtained by covering the entire triangle with a larger square and\nthen subtracting the area of the square on the hypotenuse (c). Hence:\n\na^2 + b^2 = (AB + BC) x (AB + BC) - AC x AC\n\nOn the right-hand side of the equation, (AB + BC) is equal to the length of the\nhypotenuse (c\\*\\*, since it is the longest side in a right triangle. Hence:\n\na^2 + b^2 = c x c - c x c\n\nSimplifying the right-hand side of the equation, we obtain:\n\na^2 + b^2 = c x c\n\nHence, we have proved that:\n\nc^2 = a^2 + b^2\n\nThis is Pythagoras's theorem.\n\n**Ok, that's great. Now it's time for some graph theory. Can you give me a proof\nof the 5-color theorem?**\n\nThe five color theorem states that any planar graph (a graph that can be drawn\non a plane without any of its edges crossing) can be colored with no more than\nfive colors, such that no two adjacent vertices (vertices connected by an edge)\nhave the same color.\n\nProof:\n\nConsider a planar graph G with a minimum number of vertices, and suppose that it\ncannot be colored with fewer than five colors.\n\nSince G has a minimum number of vertices, there must be a vertex v in G with the\nsmallest degree (the number of edges incident to v). Let d be the degree of v.\n\nSince G cannot be colored with fewer than five colors, d must be greater than or\nequal to 4.\n\nConsider the set of vertices adjacent to v, and let S be the set of colors that\nhave been used to color these vertices.\n\nSince the degree of v is greater than or equal to 4, the number of colors in S\nis greater than or equal to 4.\n\nSuppose, S contains all five colors. Then, since each color can be assigned to\nat most one of the vertices adjacent to v, we have a contradiction, as there are\nmore vertices than colors.\n\nHence, there must be a color not in S. Call this color c.\n\nColor vertex v with color c. Since no two adjacent vertices have the same color,\nit follows that G can be colored with no more than five colors.\n\nThis proves the five color theorem: any planar graph can be colored with no more\nthan five colors, such that no two adjacent vertices have the same color.\n\n**Ok, can you prove the 4-color theorem as well?**\n\nThe four color theorem states that any planar graph can be colored with no more\nthan four colors, such that no two adjacent vertices have the same color.\n\nProof:\n\nConsider a planar graph G and let H be a subgraph of G.\n\nWe proceed by induction on the number of vertices of H. If H has only one\nvertex, it can be colored with a single color.\n\nSuppose that the statement is true for all subgraphs of G with at most n - 1\nvertices, where n is a positive integer.\n\nLet H be a subgraph of G with n vertices, and let v be a vertex in H with the\nminimum degree.\n\nBy the induction hypothesis, all subgraphs of H with fewer than n vertices can\nbe colored with at most four colors.\n\nConsider the set of vertices adjacent to v in H, and let S be the set of colors\nused to color these vertices.\n\nIf |S| < 4, then we can color vertex v with a color not in S, and H can be\ncolored with at most four colors.\n\nOtherwise, |S| = 4. We can color v with any color not in S, and since all\nsubgraphs of H with fewer than n vertices can be colored with at most four\ncolors, it follows that H can be colored with at most four colors.\n\nHence, the statement is true for all subgraphs of G with at most n vertices.\n\nSince the statement is true for all positive integers n, it follows that any\nplanar graph can be colored with no more than four colors, such that no two\nadjacent vertices have the same color.\n\nThis proves the four color theorem: any planar graph can be colored with no more\nthan four colors, such that no two adjacent vertices have the same color.\n\n## His response?\n\nShock, really. The proof of the\n[five colour theorem](https://en.wikipedia.org/wiki/Five_color_theorem) is an\nassignment he might set in one of his early-year undergraduate classes, and the\nproof given certainly looks ok. It might well be wrong (he didn't look at it in\ndetail) but it's the sort of thing a harried marker would assume was written by\na student who had some idea of what was going on in class. The\n[four colour theorem](https://en.wikipedia.org/wiki/Four_color_theorem) is a\nmuch trickier proof---it was an unsolved research problem until 1976, when Appel and Haken famously cracked it with computer assistance. The proof\nfor that one is almost certainly wrong, but that would only be obvious to\nsomeone with considerable expertise in the domain (graph theory). Such is the\nway of LLMs.\n\nWhat does it all mean? I dunno. It's gonna be a wild decade.\n",
  "createdAt": "2026-05-13T23:14:46.061Z",
  "description": "Asking ChatGPT to prove the five colour and four colour theorems with my mathematician father-in-law, and his reaction to the results.",
  "path": "/blog/2023/02/08/writing-graph-theory-proofs-with-chatgpt",
  "publishedAt": "2023-02-08T00:00:00.000Z",
  "site": "at://did:plc:tevykrhi4kibtsipzci76d76/site.standard.publication/self",
  "tags": [
    "ai",
    "teaching"
  ],
  "textContent": "Asking ChatGPT to prove the five colour and four colour theorems with my mathematician father-in-law, and his reaction to the results.",
  "title": "Writing graph theory proofs with ChatGPT"
}