The Unit Plane Graph

Suppose we were to take the plane, \mathbb{R}^2, and turn it into a graph – not the function plotting kind, the edge and vertex kind.

We let every point in the plane be a vertex, and we draw an edge between two vertices if they are at a distance of exactly 1 from each other (Euclidean metric. We could take other metrics or other base spaces, but that is perhaps a topic for a further post).

We’ve now got a pretty formidable object! Uncountably many vertices and uncountably many edges at each vertex! But this graph is amenable enough after a little thought. Three quick ideas:


This graph is connected! Perhaps not that surprising, but the proof is a beautiful piece of intuition. For any pair of distinct points x_0, x_1, let N be the least integer greater than or equal to the distance \|x_1 - x_0\| between them. Take N many line segments of unit length and attach them to each other end-to-end. Affix one end of this chain to the point x_0.

We let the segments rotate freely at their end points, as if they were attached to each other on hinges. What we can now do is slide and bend this chain around the plane in any way we like. Wherever they lie, the line segments are guaranteed to be ‘on top of’ an edge connecting their endpoints simply by the definition of the edge set. So we simply move the other end point to coincide with x_1, and voilà!

The graph is at most 7-colourable! What? No way! Absurd – surely there are way to many points and way too many connections between them. But play around with some colouring strategies and see what you can come up with. Any set of mutually connected vertices has cardinality of at most three, spaced in an equilateral triangle. Fixing the colours of one pair of adjacent points automatically fixes the colours of all the points in that equilateral lattice tiling. This gives a pretty good hint that a triangular or hexagonal colour tiling will work. Maybe you can convince yourself that seven colours are sufficient in order to fill the tiling without any unit line segments having identically coloured endpoints.

The graph is known to be at least 4-colourable. It is not 3-colourable, for if we fix a point P (red), then let us take concentric circles of radii 1 and \sqrt{3} about it. The outer circle is either all red, in which case it has a chord of length 1 connecting two red points, or it contains points of another colour. In the latter case, let Q be such a point, coloured green, say. Then there are two points R and S on the inner circle adjacent to P and Q and to each other. The connecting edges form two back-to-back equilateral triangles with base RS and apexes P and Q. Neither R nor S can be red or green, as both connect to P and Q, but neither can they be coloured the same, as they connect to each other. So this graph is not 3-colourable.

The colouring number of this graph is actually unknown. I refer you to the Wikipedia article; apparently the colouring number may actually depend on your set-theoretic axioms! By contrast, the unit-connected line \mathbb{R} is quite easily seen to be 2-colourable.

It induces an interesting metric! The standard connected graph metric is to say that the distance between two points is the minimum number of edge traversals needed to get between them. It is only integer valued, of course, but still makes for a few moments’ contemplation. What do the open balls look like, for instance? Hint: build them inductively as unions of circles, or just consider the chain-link idea in the first point. The boundary of the closed ball of radius two consists of the closed disc of radius two minus the circle of radius one. The boundary of the closed radius-3 ball consists of the closed radius-3 disc, minus the circles of radius two and one – and so on and so forth.


What other interesting graph properties can you find here? Sure, we can ask the same questions in \mathbb{R}^3, or in stranger spaces, but this seems like a good first step. As firsts steps go, it’s quite daunting in itself – well worthy of study!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s