Download all Excel spreadsheets for this chapter.

Spreadsheets can be used to represent graphs. One basic idea is to label the edges by letters (A, B, C,...) and the vertices by numbers (1,2,3,...). We then think of each row in the spreadsheet as representing a vertex and each column as representing an edge. This is called the incidence representation of the graph. Consider, for example, the graph shown in Figure 5.1 used in the famous Seven Bridges of Königsberg problem.

Figure 5.1: Graph used in the Seven Bridges of Königsberg problem.

The incidence representation of this graph is shown in Figure 5.2. Notice, for example, that column D has a '1' occuring in row 2 and row 4 since edge D in the graph has vertices 2 and 4. In fact, this is exactly how the spreadsheet in Figure 5.2 was constructed.

Figure 5.2: The incidence representation of the graph in Figure 5.1.

Recall the following theorem regarding when a graph has an Euler circuit.

Theorem 5.1 (Euler)

(a) If a graph has any vertices of odd degree, then it cannot have an Euler circuit.
(b) If a graph is connected and every vertex has even degree, then it has at least one Euler circuit.

We can easily use a spreadsheet incidence representation of a graph to determine when a graph cannot have an Euler circuit. Figure 5.3 shows that there is not an Euler circuit for the Seven Bridges of Königsberg example. Column I simply represents the sum of the elements of rows 1 through 4 respectively. In fact, since every number in column I is odd, it shows that every vertex is of odd degree. All that was necessary was the use of the SUM command and the ability to copy the formula used in cell I1 to cells I2 through I4.

Figure 5.3: Showing the Seven Bridges of Königsberg has no Euler circuit.

Next, consider the problem of deciding when a graph has an Euler path. We must again recall a theorem due to Euler.

Theorem 5.2 (Euler)

(a) If a graph has more than two vertices of odd degree, then it cannot have an Euler path.
(b) If a graph is connected and has either zero or two vertices of odd degree, then it has at least one Euler path. Of course, if the graph has zero vertices of odd degree, then by Theorem 5.1 an Euler circuit exists.

It is clear from Figure 5.3 that the Seven Bridges of Königsberg example has no Euler path since all the vertices are of odd degree.

A graph with n vertices can also be represented as a spreadsheet having n rows and n columns. The cell in the i^th row and the j^th column is the number of edges connecting vertex i to vertex j. This is called an adjacency representation of a graph. An adjacency representation for the Seven Bridges of Königsberg example is given in Figure 5.4.

Figure 5.4: Adjacency representation of the graph for the Seven Bridges of Königsberg.

Walking

Exercise 5.1 [Excursions, Chapter 5, Exercise 1] Consider the graph shown in Figure 5.5 below.

(a) Find an incidence representation of the graph and use it to find the degree of each vertex.
(b) Find an adjacency representation of the graph and use it to find the degree of each vertex.

Figure 5.5: Graph for Exercise 5.1.

(a) Find incidence representations of each graph. Can you form a hypothesis about the incidence representations of two equivalent graphs?
(b) Find adjacency representations of each graph. Can you form a hypothesis about the adjacency representations of two equivalent graphs?

Figure 5.6: Graphs for Exercise 5.2.

Exercise 5.3 Draw a graph which has an incidence representation as given in Figure 5.7.

Figure 5.7: Spreadsheet for Exercise 5.3.

Exercise 5.4 Draw a graph which has an incidence representation as given in Figure 5.8.

Figure 5.8: Spreadsheet for Exercise 5.4.

Exercise 5.5 Draw a graph with four vertices which has an adjacency representation as given in Figure 5.9.

Figure 5.9: Spreadsheet for Exercise 5.5.

Exercise 5.6 Draw a graph with five vertices which has an adjacency representation as given in Figure 5.10.

Figure 5.10: Spreadsheet for Exercise 5.6.

Exercise 5.7 [Excursions, Chapter 5, Exercise 23] Use a spreadsheet to find the incidence representations for the three graphs in Figure 5.11. Then, use these representations and the SUM command to decide if the graphs have Euler circuits or not. Finally, use Theorem 5.2 to decide if the three graphs have Euler paths.

Figure 5.11: Graphs for Exercise 5.7.

Exercise 5.8 [Excursions, Chapter 5, Exercise 24] Use a spreadsheet to find the incidence representations for the graphs in Figure 5.12. Then, use these representations and the SUM command to decide if the graphs have Euler circuits or not. Finally, use Theorem 5.2 to decide if the graphs have Euler paths.

Figure 5.12: Graphs for Exercise 5.8.

Jogging

Exercise 5.9 Use a spreadsheet and the incidence representations for the three graphs in Figure 5.11 to illustrate the fact that the sum of the degrees of all the vertices of a graph equal twice the number of edges.

Exercise 5.10 Use a spreadsheet and the incidence representations for the three graphs in Figure 5.11 to illustrate the fact that the number of vertices of odd degree must be even.

Figure 5.13: Spreadsheet for Exercise 5.11.

For the figures in Exercise 5.7, use this spreadsheet technique to decide how many vertices of odd degree are in each graph.

Running

Exercise 5.12 For the graphs of Exercise 5.8 shown in Figure 5.12, find adjacency representations of the graphs and use them to find the degree of each vertex. Does it matter if you sum the rows or the columns? Why or why not?

Exercise 5.13 Assuming for the moment that a spreadsheet cell takes up M bytes of memory, what is the formula for the amount of memory used in making an adjacency representation with v vertices?

Exercise 5.14 What can be said about a graph when the cell located in the i^th row and i^th column of the adjacency representation of that graph is either 0 or empty?

Exercise 5.15 Describe any symmetry that the adjacency representation of a graph possesses.