Well, first of all I would like to express thanks to everyone who waited and insistently kept reminding me to post my proof here once I figure out whether it works. It doesn’t, so here it is: see if you can figure out where the mistake is (though please take the time to read and see if anyone posted the same mistake before you). The forum only allows image attachments, and I cannot extract the images from the wordpad document, so I only post text (even without subscripts and all), and I will see if I can get a moderator to attach the RTF file for me. I will reply to attempts to find the mistake and attempts to correct it time permitting.
Theorem 1
Let G be a connected planar graph. Then there is a vertex of G whose degree is at most 5. (Brualdi 516: Theorem 13.2.2)
Theorem 2
Let there be given a k-colouring of the vertices of a graph H = (U, F). Let two of the colours be red and blue, and let W be the subset of vertices in U which are assigned either the colour red or the colour blue. Let Hr, b be the subgraph of H induced by the vertices in W and let Cr, b be a connected component of Hr, b. Interchanging the colours red and blue assigned to the vertices of Cr, b, we obtain another k-colouring of H. (Brualdi 520: Theorem 13.3.1)
For plagiarism purposes, this proof was based on the four-colour proof in Brualdi.
Proof:
Let G be a planar graph of order n. Let X(G) be the chromatic number of G. If n ≤ 4, then X(G) = 4. Now, let n > 4, and the theorem is proven by induction on n. Assume G is drawn in the plane as a plane-graph. By Theorem 1, there is a vertex x whose degree is at most 5. Let H be the subgraph of order n-1 of G induced by the vertices that are different from x. By the induction hypothesis, there is a 4-colouration of H. This proof will show how to colour x so that G is four-colourable. Henceforth, the word «y-vertex» refers to yi, 1≤i≤5, an area of colour n adjacent to x:
Let p, q, r, and s denote distinct integers from 1 to 5. Let 1, 2, 3, 4, 5, a, b, c, d, and e denote colours of the map, not necessarily distinct but all one of the four colours used to colour the map. The only exception is that 1 through 5 denote integers in the following: indices of y, and when in an equation with «≡», or when preceded by «Theorem», «Case», or a form of «be».
Let H(a, b) denote the subgraph of H induced by vertices of H that are assigned either the colour a or the colour b. We say that y-vertices yp, yr Є C*(a, b) if yp and yr are in the same connected component of H(a, b), where a and b are distinct, and yp and yr are distinct and nonadjacent. We say that yp, yr Є C(a, b) if yp, yr Є C*(a, b), and yp and yr are different-coloured. (Note that «Є» implies not only set membership, but also a relationship between yp and yr.)
The condition of yp and yr to be non-adjacent, by definition of C*, allows us to define a y-vertex yq «between» them: consider p-r mod 5: if p-r ≡ 1 or ≡ 4 mod 5, yp and yr are adjacent; if p-r ≡ 0 mod 5, they are non-distinct, therefore of the same colour, a contradiction; if p-r ≡ 2 mod 5, q ≡ p-1 mod 5; if p-r ≡ 3 mod 5, q ≡ p+1 mod 5.
Given distinct colours a, b and two y-vertices yp coloured a and yr coloured e, if yp, yr Є C(a, b) (note: this means e=a or e=b), renumber so that y1 = yp, y2 = the vertex between yp and yr, y3 = yr, and the other two y-vertices are y4 and y5. Let the colour of y2 be d. Then a, b, and d are distinct. Then if a, b, c, and d are distinct, y2 cannot be in a two-colour connected component of H(c, d) with a non-adjacent y-vertex ys (so s≡4 or 5). This is because either one of y2 and ys would be inside the chain of H(a, b) connecting y1 and y2, and the other one would be outside. Also, since y4 and y5 are adjacent, they cannot be Є C*(c, d). So if a, b, c, and d are distinct, «yp, yr Є C*(a, b) implies there are no y-vertices yq, ys such that yq, ys Є C(c, d)» (keep in mind that by definition, p, q, r, and s are distinct). Note: Theorem 2 is equivalent to: if yq, ys ∉ C*(c, d), the colour of yq can be changed to that of ys without changing the colour of ys.
The requirement that a, b, c, and d be distinct is necessary because a and b are always distinct, as are c and d; if one of a or b is equal to one of c and d, say b=c, then yp, yr Є C(a, b), and yq, ys Є C(c, d), could both be true, the connected components of H(a=b, c) and H(c, d) intersecting at a vertex of colour b=c.
We say yp, yq, yr Є C(a, b) if two of yp, yq, and yr are Є C(a, b), and the third is in the same connected component of H(a, b) as the first two. Corollary: If there is only a pair of same-coloured y-vertices, then given three adjacent vertices yp coloured a, yq coloured b, and yr coloured c: yp, yq, yr ∉ C(a, b); yp, yq, yr ∉ C(b, c); yp, yq, yr ∉ C(a, c). Proof: If three vertices are in the same connected component, two of them must share a colour. Since yp and yq are adjacent, and yq and yr are adjacent, yp and yr must share a colour, so a=c. Then, given d, e Є {a, b, c}: yp, yq ∉ C(d, e) because yp and yq are adjacent; similarly, yq and yr ∉ C(d, e); last, yp, yr ∉ C(d, e) because they are of the same colour. So yp, yq, yr ∉ C(d, e).
The proof of the theorem. To start the proof, if the degree of x is 3 or less, assign the one of the 4 colours that is not adjacent to x and obtain a four-colouration of G.
Now suppose the degree of x is 4: there are 4 y-vertices adjacent to x. If two of these are of the same colour, the above process can be used to assign a colour to x and obtain a four-colouration of G. If no two y-vertices are of the same colour, consider the subgraph H(1, 3). If y1, y3 ∉ C(1, 3), apply theorem 2 to change the colour of y1 to 3. Then, there is an available colour, 1, to assign to x, resulting in a four-colouration of G. If y1, y3 Є C(1, 3), then y2, y4 ∉ C*(2, 4), by result above: either y2 is inside the chain of H(1, 3) and y4 is outside it, or vice versa. Then, apply theorem 2 to change the colour of y2 to 4, freeing the colour 2 for x and a four-colourable G. Thereby, a colour is assigned to a vertex x when its degree is 4.
Now, consider the case if the degree of x be 5. Since X(G)≡4 and degree of x is 5, at least two of the y-vertices would have to be of the same colour. If more than two y-vertices share a colour, then there are less than four colours used by them, and therefore there is a free colour to assign to x. Assign that colour to x, and the new graph is four-colourable.
If there do not exist y-vertices yp and yr such that yp, yr Є C(a, b) for some a, b, then switch the colour of a vertex yq between two vertices of the same colour to a colour of a nonadjacent vertex ys. Obviously, since there’s only a pair of same coloured vertices, yq and ys are of different colours, so were yp, yr Є C*(a, b), then also yp, yr Є C(a, b). So yp, yr ∉C*(a, b) implies the colour of ys does not change. Then, assign the previous colour of yp to x.
Now, if there exist such vertices, for the proof, first renumber so that y1, y3 Є C(a, b). This can be done because if yp, yq Є C(a, b), either p-r ≡ 2 mod 5 or p-r ≡ 3 mod 5. In the first case, number 3≡p and 1≡r; in the other case, number 1≡p, 3≡r. «Prime» the colours, which means name them 1, 2, 3, 4, and 5 such that the colour of y1 is 1, the colour of y2 is 2, &c. Now, consider all the possibilities for a, b. Case 1: If y1, y3 Є C(1, 2) or y1, y3 Є C(1, 4) or y3, y1 Є C(3, 2) or y3, y1 Є C(3, 5), then say: yp, yq Є C(a, c), yp is coloured a, yq is coloured b, yr is adjacent to yq and coloured c. Then either b=a or b=c. By definition of C, b≠a, and because yq and yr are adjacent, b≠c. Case 2: If y1, y3 Є C(1, 5), either 3=1 or 3=5; 3≠1 by definition of C; so 3=5; then, y1, y3 Є C(1, 5=3), so y2, y4 ∉ C(2, 4), so colour y2 4 and x 2. If y1, y3 Є C(3, 4), then 1≠3, so 1=4, and y1, y4 Є C*(3, 1=4). Then y2, y5 ∉ C(2, 5), so colour y5 2 and x 5. Case 3: If y1, y3 Є C(2, 4), y1, y3 Є C(2, 5), or y1, y3 Є C(4, 5), say y1, y3 Є C(a, b), and the colours of the five vertices are 1, 3, a, b, c. Since y1 and y3 are of different colours, either 1=a and 3=b or 1=b and 3=a; in either case, only 3 colours (1=a, 3=b, 5 or 1=b, 2=a, c) are used, so there is a free colour to assign to x.
The only case left is y1, y3 Є C(1, 3). Now if y1, y4 Є C*(1, 4), «shift», or renumber y4 as y1, y5 as y2, y1 as y3, y2 as y4, and y3 as y5. Prime. So y3, y5 Є C(3, 5), and y1, y3 Є C*(1, 3). Consider y1, y4. If y1, y4 Є C*(1, 4), shift and prime again. Now y1, y3 Є C*(1, 3), y3, y5 Є C*(3, 5), and y5 and y2 Є C(2, 5). If y1, y4 Є C*(1, 4), because y3, y5 Є C*(3, 5), either 1=3, 1=5, 4=3, or 4=5. Otherwise, one of y1 and y4 would be outside a chain of H(3, 5) and the other one inside, or the other way around. Because y1 and y5, y4 and y3, and y4 and y5 are adjacent, we must have 1=3. But, we have y1, y3 Є C*(1, 3), and by definition of C*, 1≠3. So we have shown that we can label the graph so that y1, y3 Є C(1, 3) and y1, y4 ∉ C*(1, 4).
Now, we consider the different same-colour combinations and show a way to colour the vertices in each case. Because their vertices are adjacent, 1≠2, 2≠3, 3≠4, 4≠5, and 1≠5. Because y1, y3 Є C(1, 3), 1≠3. If 2=5, since because we have established y1, y4 ∉ C*(1, 4), we can colour y4 1 and x 4. If 3=5, y1, y3 Є C(1, 3=5) implies y2, y4 ∉ C(2, 4), so colour y4 2 and x 4. If 1=4, then y1, y3 Є C(1=4, 3) implies y2, y5 ∉ C(2, 5), so colour y2 5 and x 2. If 2=4, then: if y3, y5 ∉ C(3, 5), colour y3 5 and x 3.
The only case left is 2=4; y1, y3 Є C(1, 3); and y3, y5 Є C(3, 5). This is the case where Alfred Kempe messed up. Now, we consider whether changing the colour of y2 to 5 would make y1, y4 Є C(1, 2=4) and whether changing the colour of y4 to 1 would make y2, y5 Є C(2=4, 5). If neither is true, simply colour y2 5, y4 1, and x 2=4. Otherwise, several options are possible. In one of them, change the colour of y2 to 1, thereby changing the colour of y1 to 2. If y1, y3 Є C(2, 3), then y2, y5 ∉ C(1, 5), so colour y2 5 and x 1. The colours of y-vertices in order are 2, 5, 3, 2, 5. If y1, y3 ∉ C(2, 3), because only the colours 1 and 2 were switched, y3, y5 Є C(3, 5), so y2, y4 ∉ C(1, 2=4), and changing the colour of y4 to 1 would not make y2, y4 Є C(1, 2=4). So colour y4 1, then y3 2 (since y1, y3 ∉ C(2, 3)), and x 3. The colours of y-vertices in order are 2, 1, 2, 1, 5. Now, numbers no longer denote colours.
The process outlined solves a long-existing problem. Whereas the 1976 proof used about 1000 hours of computer time, this proof may be followed by a mathematician in as little as half an hour.
Bibliography:
Brualdi, Richard A. Introductory Combinatorics. Upper Saddle River, NJ:
Prentice-Hall, Inc., 1999.
[/SIZE][/FONT]
Reply With Quote
Originally Posted by bleuprint
There is no way we could identify all of the possible ways there might be to open vertices and inscribe more triangles and so forth within a graph and be sure we got them all, in order to know there is now other way it can be done without obtaining an odd number of vertices, but there is a way to build up one triangle at a time. Since every face must be a triangle, including the outer region, then all edges where two triangles meet must be the same length, so that they also share the same two vertices at the ends of the same edge. That simplifies things a bit. It means that if we start with a single triangle and build up from there one triangle at a time, there are only two ways triangles can be added. Either the new triangles shares an edge with a single existing triangle, or it shares two of its edges with the edges of two existing triangles, which I will call opening a triangle and closing a triangle, respectively, as shown in the image below. 
