I was reading up on the four colour theorem and came up with a simple proof. I think it must be wrong, or probably a restatement of someone elses ideas, but I can't see the flaw...
Restatement of problem:
The statement that a graph can be coloured with n colours is equivalent to the statement that n is the largest possible number of regions which can all share a border with every other member of the set. In other words n is the largest possible number of regions where all regions touch eachother. I will call such a set of regions where each region shares a border with every other region a "community".
This can be shown by imagining a colouring in algorithm.
- Begin with an uncoloured graph which you are going to colour in with colours 1...n
- Colour in regions one at a time, always use the lowest possible colour
- Look at colour 1 - does the region border with another region with colour 1?
- If no then colour this region 1
- If yes then move to colour 2
When a region is coloured we must look at all the already coloured neighbours. If we are trying to colour something in colour n + 1 then one of two things must have happened.
Firstly all the neighbouring regions could form a community. However we have said that n is the maximum size of a community, therfore the new region must not neighbour one of the regions in the community. It can therefore be coloured the same colour as the region it is not bordering
Secondly the neighbouring regions might be formed out of several communities. Each community has at most n members and at least 2. For us to reach this state the new region must be bordering with at least n-1 communities. If any of these communities are of size less than n then it is trivial to recolour that community such that it uses a higher colour in place of one of the lower colours it already uses and hence duplicates an existing constraint on our colour choice. So we must concider the situation where we have n neighbouring communities each presenting a different colour to the boundry with our new region. Now as each community has n configurations, we need to ask - can one of the communities be re-coloured to a configuration such that the colour it has at the boundry of the new region is the same as one of the other communities without violating the colouring of the rest of the map? Well, let us examine the case where this would and would not be possible
Lets take a neighbour that is part of one of these n-communities. If it is not part of n n-comunities then we can change it's colour We could not do this if all members of the community were themselves part of another n-community. If one of them is not part of another n-community you can trivially alter it's colour, and once that colour is changed you can alter the colour
This is taking too much time - I think I need to change it. Always add a region that touches as many coloured in regions as possible - I think this is important as it means that you can only reach x by genuinely touching x different regions.
Final proof then comes from connections graph: Three connected nodes define a region. A region has an outside and an inside. Nodes inside the region can not be connected to nodes outside the region as edges would cross. Take a region defined by three nodes. To add another node to the network it must be inside or outside the original region. Once added and connected, this node and edges define three new regions. Now each region contains three nodes. As any new point added to a region can only be joined to nodes inside it's own region therefore no new nodes can be added to the network and joined to all existing nodes, as all nodes are outside of at least one region.
