7.02b Graph terminology: tree, simple, connected, simply connected

7

1. A simple connected graph \(X\) has eight vertices.
   1. State the minimum number of edges of the graph.
   2. Find the maximum number of edges of the graph.
2. A simple connected graph \(Y\) has \(n\) vertices.
   1. State the minimum number of edges of the graph.
   2. Find the maximum number of edges of the graph.
3. A simple graph \(Z\) has six vertices and each of the vertices has the same degree \(d\).
   1. State the possible values of \(d\).
   2. If \(Z\) is connected, state the possible values of \(d\).
   3. If \(Z\) is Eulerian, state the possible values of \(d\).

3 Consider the following algorithm.
Step 1: Input a positive integer \(n\).
Step 2 : Draw a graph consisting of \(n\) vertices and no arcs.
Step 3 : Create a new vertex and join it directly to every vertex of order 0.
Step 4: Create a new vertex and join it directly to every vertex of odd order.
Step 5 : Stop.

1. Draw separate diagrams to show the result of applying this algorithm in the following cases.
   1. \(n = 1\)
   2. \(n = 2\)
   3. \(n = 3\)
   4. \(n = 4\)
   5. State how many arcs are in the graph that results when the algorithm is applied to a set of \(n\) vertices.

3 A simple graph is one in which any two vertices are directly connected by at most one arc and no vertex is directly connected to itself. A connected graph is one in which every vertex is connected, directly or indirectly, to every other vertex. A simply connected graph is one that is both simple and connected.

1. A simply connected graph is drawn with 6 vertices and 9 arcs.
   1. What is the sum of the orders of the vertices?
   2. Explain why if the graph has two vertices of order 5 it cannot have any vertices of order 1.
   3. Explain why the graph cannot have three vertices of order 5 .
   4. Draw an example of a simply connected graph with 6 vertices and 9 arcs in which one of the vertices has order 5 and all the orders of the vertices are odd numbers.
   5. Draw an example of a simply connected graph with 6 vertices and 9 arcs that is also Eulerian.

2

1. Draw a graph with five vertices of orders 1, 2, 2, 3 and 4 .
2. State whether the graph from part (i) is Eulerian, semi-Eulerian or neither. Explain how you know which it is.
3. Explain why a graph with five vertices of orders \(1,2,2,3\) and 4 cannot be a tree.

2 A simple graph is one in which any two vertices are directly connected by at most one arc and no vertex is directly connected to itself. A connected graph is one in which every vertex is joined, directly or indirectly, to every other vertex.
A simply connected graph is one that is both simple and connected.

1. Explain why there is no simply connected graph with exactly five vertices each of which is connected to exactly three others.
2. A simply connected graph has five vertices \(A , B , C , D\) and \(E\), in which \(A\) has order \(4 , B\) has order 2, \(C\) has order 3, \(D\) has order 3 and \(E\) has order 2. Explain how you know that the graph is semi-Eulerian and write down a semi-Eulerian trail on this graph. A network is formed from the graph in part (ii) by weighting the arcs as given in the table below.

   	\(A\)	\(B\)	\(C\)	\(D\)	\(E\)
   \(A\)	-	5	3	8	2
   \(B\)	5	-	6	-	-
   \(C\)	3	6	-	7	-
   \(D\)	8	-	7	-	9
   \(E\)	2	-	-	9	-

3. Apply Prim's algorithm to the network, showing all your working, starting at vertex \(A\). Draw the resulting tree and state its total weight. A sixth vertex, \(F\), is added to the network using arcs \(C F\) and \(D F\), each of which has weight 6 .
4. Use your answer to part (iii) to write down a lower bound for the length of the minimum tour that visits every vertex of the extended network, finishing where it starts. Apply the nearest neighbour method, starting from vertex \(A\), to find an upper bound for the length of this tour. Explain why the nearest neighbour method fails if it is started from vertex \(F\).

3

1. Explain why it is impossible to draw a graph with exactly four vertices of orders 1, 2, 3 and 3 . A simple graph is one in which any two vertices are directly connected by at most one arc and no vertex is directly connected to itself. A connected graph is one in which every vertex is joined, directly or indirectly, to every other vertex.
   A simply connected graph is one that is both simple and connected.
2. Explain why there is no simply connected graph with exactly four vertices of orders \(1,1,2\) and 4.
3. A connected graph has four vertices \(A , B , C\) and \(D\), in which \(A , B\) and \(C\) have order 2 and \(D\) has order 4. Explain how you know that the graph is Eulerian. Draw an example of such a graph and write down an Eulerian trail for your graph. A graph has three vertices, \(A , B\) and \(C\) of orders \(a , b\) and \(c\), respectively.
4. What restrictions on the values of \(a , b\) and \(c\) follow from the graph being
   1. simple,
   2. connected,
   3. semi-Eulerian?
      1. Describe carefully how to carry out the first pass through bubble sort when we are using it to sort a list of \(n\) numbers into increasing order. State which value is guaranteed to be in its correct final position after the first pass and hence explain how to carry out the second pass on a reduced list. Write down the stopping condition for bubble sort.
      2. Show the list of six values that results at the end of each pass when we use bubble sort to sort this list into increasing order. $$\begin{array} { l l l l l l } 3 & 10 & 8 & 2 & 6 & 11 \end{array}$$ You do not need to count the number of comparisons and the number of swaps that are used. Zack wants to cut lengths of wood from planks that are 20 feet long. The following lengths, in feet, are required. $$\begin{array} { l l l l l l } 3 & 10 & 8 & 2 & 6 & 11 \end{array}$$
      3. Use the first-fit method to find a way to cut the pieces.
      4. Use the first-fit decreasing method to find a way to cut the pieces. Give a reason why this might be a more useful cutting plan than that from part (iii).
      5. Find a more efficient way to cut the pieces. How many planks will Zack need with this cutting plan and how many cuts will he need to make? 5 An online shopping company selects some of its parcels to be checked before posting them. Each selected parcel must pass through three checks, which may be carried out in any order. One person must check the contents, another must check the postage and a third person must check the address. The parcels are classified according to the type of customer as 'new', 'occasional' or 'regular'. The table shows the time taken, in minutes, for each check on each type of parcel.
         1. Since \(a \leqslant 6\) it follows that \(6 - a \geqslant 0\), and similarly for \(b\) and \(c\). Let \(6 - a = x\) (so that \(a\) is replaced by \(6 - x ) , 8 - b = y\) and \(10 - c = z\) to show that the problem can be expressed as $$\begin{array} { l l } \text { Maximise } & 2 x - 4 y + 5 z , \\ \text { subject to } & 3 x + 2 y - z \leqslant 14 , \\ & 2 x - 4 z \leqslant 7 , \\ & - 4 x + y \leqslant 4 , \\ \text { and } & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 . \end{array}$$
         2. Represent the problem as an initial Simplex tableau. Perform two iterations of the Simplex algorithm, showing how each row was obtained. Hence write down the values of \(a , b\) and \(c\) after two iterations. Find the value of the objective for the original problem at this stage.
            [0pt] [10]

2 A tetromino is a two-dimensional shape made by joining four squares edge-to-edge. Joins are along complete edges.

1. Represent each of the tetrominoes below by a graph in which the nodes represent the squares and two nodes are joined by an arc if the squares share a common edge. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_76_268_1206_420} \captionsetup{labelformat=empty} \caption{(A)}
   \end{figure} \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_145_208_1201_836} \captionsetup{labelformat=empty} \caption{(B)}
   \end{figure} \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_145_144_1201_1165} \captionsetup{labelformat=empty} \caption{(C)}
   \end{figure} \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_145_209_1201_1439} \captionsetup{labelformat=empty} \caption{(D)}
   \end{figure}
2. Six simply connected graphs with four nodes are shown below. For each graph, either draw a tetromino that can be represented by the graph, as in part (i), or explain why this is not possible. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_122_126_1603_299} \captionsetup{labelformat=empty} \caption{(1)}
   \end{figure} \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_122_209_1603_529} \captionsetup{labelformat=empty} \caption{(2)}
   \end{figure} \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_122_125_1603_840} \captionsetup{labelformat=empty} \caption{(3)}
   \end{figure} \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_122_127_1603_1082} \captionsetup{labelformat=empty} \caption{(4)}
   \end{figure} \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_122_122_1603_1343} \captionsetup{labelformat=empty} \caption{(5)}
   \end{figure} \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_122_122_1603_1603} \captionsetup{labelformat=empty} \caption{(6)}
   \end{figure} Two tetrominoes are regarded as being the same if one can be rotated or reflected to form the other. Derek claims that each tetromino corresponds to a unique tree with four nodes, and each tree with four nodes corresponds to a unique tetromino. Derek's claim is wrong.
3. From the diagrams above, find:
   1. a tetromino whose graph does not correspond to a tree;
   2. two different tetrominoes whose graphs correspond to the same tree. A pentomino is a two-dimensional shape made by joining five squares edge-to-edge. Joins are along complete edges. Two pentominoes are regarded as being the same if one can be rotated or reflected to form the other. There are twelve distinct pentominoes.
   3. When the pentominoes are represented by graphs, as in part (i), there are only four distinct graphs. Draw these four graphs.

2 A simple graph is one which has no repeated arcs and no arc that joins a vertex to itself.

1. Draw a simple graph that connects four vertices using five arcs.
2. Explain why, in any graph, there must be an even number of odd vertices.
3. By considering the orders of the vertices, show that there is only one possible simple graph that connects four vertices using five arcs.

2

1. Draw three mathematically different graphs, labelled graph \(A\), graph \(B\) and graph \(C\), each with four vertices, of orders 1, 3, 3 and 3, and five arcs.
2. Explain how you know that none of the graphs from part (i) is Eulerian.

1 Two graphs A and B are shown below. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure}

1. Write down an example of a cycle on graph A .
2. W hy is \(\mathrm { U } - \mathrm { Y } - \mathrm { V } - \mathrm { Z } - \mathrm { Y } - \mathrm { X }\) not a path on graph B ?
3. How many arcs would there be in a spanning tree for graph A ?
4. For each graph state whether it is Eulerian, semi-Eulerian or neither.
5. The graphs show designs to be etched on metal plates. The etching tool is positioned at a starting point and follows a route without repeating any arcs. It may be lifted off and positioned at a new starting point. W hat is the smallest number of times that the etching tool must be positioned, including the initial position, to draw each graph? An arc is drawn connecting Q to U , so that the two graphs become one. The resulting graph is not Eulerian.
6. Extra arcs are then added to make an Eulerian graph. W hat is the smallest number of extra arcs that need to be added?

2 A simple graph is one in which any two vertices are directly connected by at most one arc and no vertex is directly connected to itself. A connected graph is one in which every vertex is joined, directly or indirectly, to every other vertex.
A simply connected graph is one that is both simple and connected.

1. Explain why it is impossible to draw a graph with exactly three vertices in which the vertex orders are 2, 3 and 4.
2. Draw a graph with exactly four vertices of orders 1, 2, 3 and 4 that is neither simple nor connected.
3. Explain why there is no simply connected graph with exactly four vertices of orders \(1,2,3\) and 4. State which of the properties 'simple' and 'connected' cannot be achieved.
4. A simply connected Eulerian graph has exactly five vertices.
   1. Explain why there cannot be exactly three vertices of order 4.
   2. By considering the vertex orders, explain why there are only four such graphs. Draw an example of each.

3 A simple graph is one in which any two vertices are directly connected by at most one arc and no vertex is directly connected to itself. A connected graph is one in which every vertex is joined, directly or indirectly, to every other vertex.
A simply connected graph is one that is both simple and connected.

1. Explain why it is impossible to draw a graph with exactly five vertices of orders \(1,2,3,4\) and 5.
2. Explain why there is no simply connected graph with exactly five vertices of orders \(2,2,3,4\) and 5 . State which of the properties 'simple' and 'connected' cannot be achieved.
3. Calculate the number of arcs in a simply connected graph with exactly five vertices of orders 1 , 1, 2, 2 and 4 . Hence explain why such a graph cannot be a tree.
4. Draw a simply connected semi-Eulerian graph with exactly five vertices that is also a tree. By considering the orders of the vertices, explain why it is impossible to draw a simply connected Eulerian graph with exactly five vertices that is also a tree. In the graph below the vertices represent buildings and the arcs represent pathways between those buildings. \includegraphics[max width=\textwidth, alt={}, center]{cec8d4db-4a72-43a3-88f3-ff9df2a11d2c-4_426_1081_1297_532}
5. By considering the orders of the vertices, explain why it is impossible to walk along these pathways in a continuous route that uses every arc once and only once. Write down the minimum number of arcs that would need to be travelled twice to walk in a continuous route that uses every arc at least once.

2 A simple graph is one in which any two vertices are directly connected by at most one arc and no vertex is directly connected to itself. A connected graph is one in which every vertex is joined, directly or indirectly, to every other vertex. A simply connected graph is one that is both simple and connected.

1. (a) Draw a simply connected Eulerian graph with exactly five vertices and five arcs.
   (b) Draw a simply connected semi-Eulerian graph with exactly five vertices and five arcs, in which one of the vertices has order 4.
   (c) Draw a simply connected semi-Eulerian graph with exactly five vertices and five arcs, in which none of the vertices have order 4. A teacher is organising revision classes for her students. There will be ten revision classes scheduled into a number of sessions. Each class will run in one session only. Each student has chosen two classes to attend. The table shows which classes each student has chosen. \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Revision classes}

   Student number	C1	C2	C3	C4	M1	M2	S1	S2	D1	D2
   1	✓	✓
   2				✓						✓
   3			✓	✓
   4			✓			✓
   5								✓	✓
   6		✓				✓
   7					✓			✓
   8	✓						✓
   9						✓				✓
   10					✓		✓

   \end{table}
2. (a) Draw a graph to show this information. Each vertex represents a class. Each arc links the two classes chosen by a student.
   (b) Show how the teacher can arrange the classes in just two sessions, which satisfy all student choices. For example, C1 and C2 cannot be in the same session. An extra student joins the group. This student chooses to attend the revision classes in M1 and D1.
   (c) Explain why the teacher cannot now arrange the classes in just two sessions. Do not amend your graph from part (ii)(a).

2 A simple graph is one in which any two vertices are directly connected by at most one arc and no vertex is directly connected to itself. A connected graph is one in which every vertex is joined, directly or indirectly, to every other vertex. A simply connected graph is one that is both simple and connected.

1. (a) Draw a connected Eulerian graph that has exactly four vertices and five arcs but is not simple.
   (b) Explain why it is not possible to have a simply connected Eulerian graph with exactly four vertices and five arcs. A simply connected Eulerian graph is drawn that has exactly eight vertices and ten arcs.
2. (a) Explain how you know that the sum of the vertex orders must be 20 .
   (b) Write down the minimum and maximum possible vertex order and draw a diagram that includes both the minimum and the maximum cases.
   (c) Draw a diagram to show a simply connected Eulerian graph with exactly eight vertices and ten arcs in which the number of vertices of order 4 is as large as possible.

2 A simple graph is one in which any two vertices are directly connected by at most one arc and no vertex is directly connected to itself. A connected graph is one in which every vertex is joined, directly or indirectly, to every other vertex. A simply connected graph is one that is both simple and connected.

1. (a) Draw a simply connected graph that has exactly four vertices and exactly five arcs. Is your graph Eulerian, semi-Eulerian or neither? Explain how you know.
   (b) By considering the sum of the vertex orders, show that there is only one possible simply connected graph with exactly four vertices and exactly five arcs.
2. Draw five distinct simply connected graphs each with exactly five vertices and exactly five arcs.

6 The Devil's Dice are four cubes with faces coloured green, yellow, blue or red.
Cube 1 has three green faces and one each of yellow, blue and red.

• Two of the green faces are opposite one another.
• The other green face is opposite the yellow face.
• The blue face is opposite the red face.

This information is represented using the graph in Fig. 1. \begin{figure}[h] \end{figure} Fig. 1

1. Cube 2 has a green face opposite a blue face, another green face opposite a red face and a second red face opposite a yellow face. Draw a graph to represent this information. The graph in Fig. 2 represents opposite faces in cube 3. Cube 3 \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{372c062a-793f-4fb8-a769-957479f5fce7-08_350_326_1398_986} \captionsetup{labelformat=empty} \caption{Fig. 2}
   \end{figure}
2. How many yellow faces does cube 3 have? Cube 4 has one green face, two yellow faces, one blue face and two red faces. The graph in Fig. 3 is an incomplete representation of opposite faces in cube 4 . \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Cube 4} \includegraphics[alt={},max width=\textwidth]{372c062a-793f-4fb8-a769-957479f5fce7-08_257_273_2115_1018}
   \end{figure} Fig. 3
3. Complete the graph in your answer book. The Devil's Dice puzzle requires the cubes to be stacked to form a tower so that each long face of the tower uses all four colours. The puzzle can be solved using graph theory. First the graphs representing the opposite faces of the four cubes are combined into a single graph. The edges of the graph are labelled \(1,2,3\) or 4 to show which cube they belong to. The labelled graph in Fig. 4 shows cube 1 and cube 3 together. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{372c062a-793f-4fb8-a769-957479f5fce7-09_630_689_625_689} \captionsetup{labelformat=empty} \caption{Fig. 4}
   \end{figure}
4. Complete the copy of the labelled graph in your answer book to show all four cubes. A subgraph is a graph contained within a given graph.
   From the graph representing all four cubes a subgraph needs to be found that will represent the front and back faces of the tower. Each face of the tower uses each colour once. This means that the graph representing the front and back faces must be a subgraph of the answer to part (iv) with four edges labelled \(1,2,3\) and 4 and four nodes each having order two.
5. Explain why if the loop labelled 1 joining G to G is used, it is not possible to form a subgraph with four edges labelled 1, 2, 3 and 4 and nodes each having order two. Suppose that the edge labelled 1 that joins B and R is used.
6. Draw a subgraph that has the required properties and uses the edge labelled 1 that joins B and R .
7. Using your answer to part (vi), show the two possible colourings of the back of the tower.

4 A simple graph is one in which any two vertices are directly connected by at most one arc and no vertex is directly connected to itself. A connected graph is one in which every vertex is joined, directly or indirectly, to every other vertex. A simply connected graph is one that is both simple and connected. Molly says that she has drawn a graph with exactly five vertices, having vertex orders 1, 2, 3, 4 and 5.

1. State how you know that Molly is wrong. Holly has drawn a connected graph with exactly six vertices, having vertex orders 2, 2, 2, 2, 4 and 6.
2. (a) Explain how you know that Holly's graph is not simply connected.
   (b) Determine whether Holly's graph is Eulerian, semi-Eulerian or neither, explaining how you know which of these it is. Olly has drawn a simply connected graph with exactly six vertices.
3. (a) State the minimum possible value of the sum of the vertex orders in Olly's graph.
   (b) If Olly's graph is also Eulerian, what numerical values can the vertex orders take? Polly has drawn a simply connected Eulerian graph with exactly six vertices and exactly ten arcs.
4. (a) What can you deduce about the vertex orders in Polly's graph?
   (b) Draw a graph that fits the description of Polly's graph.

3 Consider the following graph in which the arcs are straight lines. \includegraphics[max width=\textwidth, alt={}, center]{71ca9c4e-573b-43b7-910d-4bd610af6b27-3_928_938_317_566}

1. Explain how you know that the graph is simple.
2. Explain how you know that the graph is not connected.
3. On the copy of the graph in your answer book, add as many arcs as you can whilst keeping it both simple and not connected. Give the number of arcs which you have added.
4. Imagine that a new graph is produced in which two vertices are connected if there is no connection between them, direct or indirect, on the original graph. How many arcs would this new graph have?

1 The diagram shows an electrical circuit with wires and switches and with five components, labelled A, B, C, D and E. \includegraphics[max width=\textwidth, alt={}, center]{11c2d98f-1f72-4f1b-b971-5521bee09358-2_328_730_609_319} \includegraphics[max width=\textwidth, alt={}, center]{11c2d98f-1f72-4f1b-b971-5521bee09358-2_261_519_621_1224}

1. Draw a graph showing which vertices are connected together, either directly or indirectly, when the two switches remain open.
2. How many arcs need to be added to your graph when both switches are closed? The graph below shows which components are connected to each other, either directly or indirectly, for a second electrical circuit. \includegraphics[max width=\textwidth, alt={}, center]{11c2d98f-1f72-4f1b-b971-5521bee09358-2_410_494_1356_788}
3. Find the minimum number of arcs which need to be deleted to create two disconnected sets of vertices, and write down your two separate sets.
4. Explain why, in the second electrical circuit, it might be possible to split the components into two disconnected sets by cutting fewer wires than the number of arcs which were deleted in part (iii).

1 A graph is obtained from a solid by producing a vertex for each exterior face. Vertices in the graph are connected if their corresponding faces in the original solid share an edge. The diagram shows a solid followed by its graph. The solid is made up of two cubes stacked one on top of the other. This solid has 10 exterior faces, which correspond to the 10 vertices in the graph. (Note that in this question it is the exterior faces of the cubes that are being counted.) \includegraphics[max width=\textwidth, alt={}, center]{3239d012-5699-4789-ba64-f1295f4b4642-2_455_309_571_653} \includegraphics[max width=\textwidth, alt={}, center]{3239d012-5699-4789-ba64-f1295f4b4642-2_444_286_573_1135}

1. Draw the graph for a cube.
2. Obtain the number of vertices and the number of edges for the graph of three cubes stacked on top of each other. \includegraphics[max width=\textwidth, alt={}, center]{3239d012-5699-4789-ba64-f1295f4b4642-2_643_305_1302_881}

2 A small party is held in a country house. There are 10 men and 10 women, and there are 10 dances. For each dance a number of pairings, each of one man and one woman, are formed. The same pairing can appear in more than one dance. A graph is to be drawn showing who danced with whom during the evening, ignoring repetitions.

1. Name the type of graph which is appropriate.
2. What is the maximum possible number of arcs in the graph? Dashing Mr Darcy dances with every woman except Elizabeth, who will have nothing to do with him. She dances with eight different men. Prince Charming only dances with Cinderella. Cinderella only dances with Prince Charming and with Mr Darcy. The three ugly sisters only have one dance each.
3. Add arcs to the graph in your answer book to show this information.
4. What is the maximum possible number of arcs in the graph?

2 Fig. 2.1 represents the two floors of a house. There are 5 rooms shown, plus a hall and a landing, which are to be regarded as separate rooms. Each " × " represents an internal doorway connecting two rooms. The " ⊗ " represents the staircase, connecting the hall and the landing. \begin{figure}[h] \end{figure}

1. Draw a graph representing this information, with vertices representing rooms, and arcs representing internal connections (doorways and the stairs). What is the name of the type of graph of which this is an example?
2. A larger house has 12 rooms on two floors, plus a hall and a landing. Each ground floor room has a single door, which leads to the hall. Each first floor room has a single door, which leads to the landing. There is a single staircase connecting the hall and the landing. How many arcs are there in the graph of this house?
3. Another house has 12 rooms on three floors, plus a hall, a first floor landing and a second floor landing. Again, each room has a single door on to the hall or a landing. There is one staircase from the hall to the first floor landing, and another staircase joining the two landings. How many arcs are there in the graph of this house?
4. Fig. 2.2 shows the graph of another two-floor house. It has 8 rooms plus a hall and a landing. There is a single staircase. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{c429bfed-9241-409a-9cd5-9553bf16c9df-3_208_666_1896_694} \captionsetup{labelformat=empty} \caption{Fig. 2.2}
   \end{figure} Draw a possible floor plan, showing internal connections.

1 Bus routes connect towns A and B and towns A and C .
Train lines connect towns B and D, towns C and D, and towns A and C.
John represents this information in a graph with four nodes, one for each town, in which an arc is drawn for each connection, giving five arcs in all.

1. Draw John's graph.
2. Is John's graph simple? Justify your answer. Jamil represents the information in a graph with five nodes. He uses one node for each of towns A, B and D. Because in town C the bus station and train station are some distance apart, he uses a node labelled C (bus) and a node labelled C (train). Again there are 5 arcs, each representing a connection.
3. Draw Jamil's graph.
4. Is Jamil's graph a tree? Justify your answer.

3 The graph represents four towns together with (two-way) roads connecting them. \includegraphics[max width=\textwidth, alt={}, center]{8eba759f-38bc-4d14-ac65-9a0ee6c79741-4_191_286_319_886} A path is a set of connected arcs linking one vertex to another. A path contains no repeated vertex. \(\mathrm { T } _ { 1 } \rightarrow \mathrm {~T} _ { 2 }\) and \(\mathrm { T } _ { 1 } \rightarrow \mathrm {~T} _ { 3 } \rightarrow \mathrm {~T} _ { 2 }\) are paths.

1. There are six paths from \(\mathrm { T } _ { 1 }\). List them.
2. List the paths from \(\mathrm { T } _ { 4 }\).
3. How many paths are there altogether? For this question a route is defined to be a path in which the direction of the arcs is not relevant. Thus \(\mathrm { T } _ { 1 } \rightarrow \mathrm {~T} _ { 2 }\) and \(\mathrm { T } _ { 2 } \rightarrow \mathrm {~T} _ { 1 }\) are the same route. Similarly \(\mathrm { T } _ { 1 } \rightarrow \mathrm {~T} _ { 3 } \rightarrow \mathrm {~T} _ { 2 }\) and \(\mathrm { T } _ { 2 } \rightarrow \mathrm {~T} _ { 3 } \rightarrow \mathrm {~T} _ { 1 }\) are the same route (but note that \(\mathrm { T } _ { 1 } \rightarrow \mathrm {~T} _ { 2 } \rightarrow \mathrm {~T} _ { 3 }\) is different).
4. How many routes are there altogether?

1 Two students draw graphs to represent the numbers of pairs of shoes owned by members of their class. Andrew produces a bipartite graph, but gets it wrong. Barbara produces a completely correct frequency graph. Their graphs are shown below. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure}

1. Draw a correct bipartite graph.
2. How many people are in the class?
3. How many pairs of shoes in total are owned by members of the class?
4. Which points on Barbara's graph may be deleted without losing any information? Charles produces the same frequency graph as Barbara, but joins consecutive points with straight lines.
5. Criticise Charles's graph.