Examples

Before giving definitions, it may be helpful to consider examples of each.

The first example is of land borders within the EU. Vertices are countries and edges are land borders between them. This is an undirected graph, because there is no preferred direction for border crossings.

The second example has as its vertices the substrings of the word mathematics which are themselves words. There is an edge from one word to another if the second occurs as a proper substring of the first without any other word appearing in between. This is a directed graph because the “is a proper substring of” relation is not symmetric. You might notice that this graph is very nearly a tree. It only fails to be because the word mat appears twice in mathematics. The first occurrence is a proper substring of mathematics but not a proper substring of any proper substring which is a word. The second occurrence is a proper substring of the word thematic.

Note that the graph is defined by which vertices are connected by an edge, not by its visual representation in a particular diagram. There are edges which cross in our directed graph example. This could have been avoided by rearranging the positions of some vertices and edges but the crossings are in any case just artifacts of the particular visual representation, not features of the graph. A graph which can be drawn in the plane without edge crossings is called planar. So the EU border graph is planar, even though this particular diagram has edge crossings. Not all graphs are planar though. Our third example, with seven vertices and an edge between each pair of vertices, is not. Proving that a graph isn’t planar is not straightforward though, since the presence of edge crossings in some particular diagram doesn’t really tell you anything. The only way to prove this is to prove that all planar graphs have some property which all planar graphs have and then show that this graph doesn’t have it.

You can find a number of other examples of graphs in earlier chapters. All trees are graphs. Also, all of our state diagrams for idealised machines are graphs, provided we make one change, which is described below.