Peculiar planar graphs inside a vertex (Re-posting)

From an idea developed May 20th 2013

Peculiar planar graphs inside a vertex

Keith J. Tinkler

Abstract

A peculiar sub-graph of planar graphs is described (Peculiar graphs) each of which is attached by a cut-point vertex to a ‘normal’ planar graph G, but that is otherwise unconnected with it. Happily the new class does not disturb colour theorems, either within the Peculiar graph, or by way of attachment to ‘normal’ planar graphs. However, any graph that contains a Peculiar graph will fail to satisfy the Euler relation:  v + f = e + 2 (where v = #vertices, f = #faces, e = #edges). The numerical difference is a measure of the planar graph’s peculiarity.

The existence of this new class may have been overlooked – perhaps because the visual impression of the procedure that generates a peculiar graph from the standard vertex and edge representation of a geographic map seems forced and unnatural (e.g. see Fig. 4). However it emerges naturally enough from a consideration of actual maps. They may not be politically sensible maps – but they are legitimate maps! However it then poses problems about how to represent them properly as graphs.

Building a planar graph G by expansion

Begin with a single vertex.

PP Figure 1

Consider how to expand this map or graph by adding a new country or vertex, i.e. two countries with a common boundary:

So far so good. Now consider that another map option is (e.g. The Vatican inside Italy, and others too).

PP Figure 2a and b

This situation cannot be satisfactorily handled by the previous graph for two countries. It looks as though it can – but clearly the inside orange country in the map cannot connect to any new countries added outside the collar if planarity is to be maintained. This is not apparent if we use the previous graph (Fig. 2b).

PP Figure 3a & b

Two solutions are possible for representation.

  1. Use the previous representation with the understanding that any further vertices expanded from the orange vertex cannot connect to any expansion based on the green node.

This would be satisfactory except that a nuance in counting faces for the Euler relation might be missed.

A fuller representation is:

PP Fig. 4 replacement

(ii) From the map representation above it is clear that the circumferential green is better shown as a ring or collar to which the orange country is attached inside.

This representation clearly displays the inside face (F2). It might be argued that this assignation of F2 is not legitimate. But F1 exists as the exterior face while the green vertex is still an isolated node. When a new vertex is added in F1 and an edge drawn to connect the two, F1 still exists as a single entity. If a vertex is added to the interior of the green vertex we must extend to any such new vertex added inside the same condition. In effect it is most easily interpreted as a freedom to expand.  Recall the triangular face of a graph represents a triple junction in a map. Thus the orange vertex is surrounded by a new face, F2.

Checking this graph against the Euler relation:

2 + 2 ≠ 1 + 2;  the relation fails in its present form.

A consequence is that the relation fails in whatever manner the graph is expanded. Expanding G outwards into F1 from the green collar – the normal procedure as is well known – will always increment the graph in such a way that the Euler Theorem is satisfied. However, if there also exists an interior vertex and face then the failing inequality at the very first step (which already includes the normal terms from G ), will ensure it fails for the entire graph.

Lemma: Any planar graph that fails to satisfy the Euler relation contains a ‘Peculiar’ graph.

If graphs have not been constructed on this premise before, then it is unlikely that the failure mentioned in the Lemma will have been discovered.

I suggest the adjective Peculiar for these graphs because with Church of England Dioceses it was not unusual for any given Diocese (the territory of a Bishopric) to have outliers entirely surrounded by another Diocese. Such an outlier is termed a Peculiar.

Representation (i) could still be used with the proviso given, and the additional requirement that the exterior face (only) counts for 2 in the Euler relation, and bearing in mind that further peculiar expansions might be made from vertices in either graph, each adding an additional face. A more fanciful representation might be to draw the Peculiar graph on a separate vertical plane rooted – in this example – at the green collar node.

Colouring

A planar graph expanded from the orange vertex will be no different from any other planar graph – so the four color theorem will still apply. Only the collar node connects the Peculiar graph to the the normal graph, however expanded outside. It thus constitutes a cut-point vertex. However the normal and Peculiar graphs may be coloured it is a simple matter to rotate the successful colourings  within either so that the cut-point has the same colour in both graphs.

Expansion from either vertex

The previous section has covered expansion from a single vertex. It follows that either existing vertex can be expanded in the same fashion as either Fig 2a, or 3a. Following 2a leads to a normal planar graph where the two colours in Fig. 2b simply indicate separate colours. Following Fig. 3a and Fig. 4 for the orange vertex adds another Peculiar graph to the entire planar graph. The failure of the Euler relation stems entirely from an ‘interior’ expansion, and every such expansion (from any vertex whatever) leads to an additional ‘falling short’ in the computed relation by 1. This leads to:

Lemma 2

The numerical difference, P, between the computed relation, and the expected Euler relation counts the number of Peculiar graphs attached to the entire graph.

Thus there is a need for a modification, Ep, of the Euler relation:

Ep     =   v  + f = e + 2 + P,

where P is the number of Peculiar graphs attached to the regular graph. P can used as a peculiarity index of G that might be appended to G as some sort of subscript or superscript, if thought necessary.

Expansion continued

The orange vertex might be expanded outwards into F2 (not diagrammed) just as the green vertex can be extended into F1 with say the yellow vertex. The green vertex can be expanded into F2  to give a blue vertex without creating another face because it already exists. The inequality remains in the Euler relation – the difference still being 1. The corresponding maps and graphs are now, for example:

PP Figure 5

with one extra vertex in each of F1 and F2. Note that in the graph representation on the right that F2 cannot be easily represented. The yellow vertex (in F1) could well be coloured either orange or blue because normal colouring rules apply.

If we require the graph to become fully connected we get:

PP Figure 6a & b

The peculiarity of the graph prevents the yellow node connecting to the {blue, orange} part of the sub-graph as would be the case for a normal planar graph. Although F2 is not easily represented in the right hand diagram without additional markings, the new F3 face can be marked without ambiguity.

Matrix representation

The green vertex as noted above is a cut-point vertex. It follows that in adjacency matrix, A(G), representing G (Fig. 6a), there will a single link to the peculiar subgraph. Labeling the vertices by their colours the graph will appear as:

PP Figure 7

The highlighted link connects the YG subgraph to the GOB peculiar subgraph via the green, G, cut-point vertex.

A slightly bigger example (row and column numbering implicit).

PP Figure 8a & b

Assume the graphs are fully connected subject to the restrictions introduced by the peculiar condition. Then 4 is the point of expansion of the peculiar subgraph leading to 5 (because {1,2,3,4} are completely connected), that itself expands to the completely connected subgraph {6,7}. Recall that each expansion introduces a new face, then the Euler number is:

7 + 6 ≠ 9 + 2, difference is 2. The graph G has peculiarity index 2.

By definition the planar graph is fully connected, thus the fact that 6 and 7 do not connect to 4 implies that 5 is enclosed within 4 as a separate peculiar extension and that 6 and 7 are contained within the enclosure provided by 5.

The map implied by the graph follows.

PP Figure 9

That tempts us draw a child’s picture of face and compute its peculiarity! It may be peculiar, but it is a legitimate map (& child).

The original stimulus for this exposition arose from exploring procedures for generating fully connected planar graphs, and colouring them as they develop. It was obvious that expansion could occur by placing a new vertex in a face, on an existing edge, and I finally realized, inside a vertex. Edges are then added to complete the requirement that the planar graph be fully connected. It was a surprise to find, via standard arguments about locally finite planar graphs applied to Fig. 3a, that a countable infinite planar graph exists with a countably infinite peculiarity!

I do not know at present whether these peculiar graphs have any further interesting properties. I suspect they do not.

References

I know of none on this peculiarity. Texts consulted are:

Harary, F., 1969. Graph Theory, Addison-Wesley, 273p.

Wilson, R.J., 1972. Introduction to Graph Theory, Oliver & Boyd, 168p.

Wilson, R.J., 2002, Four Colors Suffice. Princeton University Press, 262p.

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