Impossibility proofs for degree sequences

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 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 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.

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.

1. Explain why it is impossible to draw a graph with four vertices in which the vertex orders are 1, 2, 3 and 3. [1]

A simple graph is one in which any two vertices are directly joined by at most one arc and no vertex is directly joined 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. 1. Draw a graph with five vertices of orders 1, 1, 2, 2 and 4 that is neither simple nor connected. [2]
   2. Explain why your graph from part (a) is not semi-Eulerian. [1]
   3. Draw a semi-Eulerian graph with five vertices of orders 1, 1, 2, 2 and 4. [1]

Six people (Ann, Bob, Caz, Del, Eric and Fran) are represented by the vertices of a graph. Each pair of vertices is joined by an arc, forming a complete graph. If an arc joins two vertices representing people who have met it is coloured blue, but if it joins two vertices representing people who have not met it is coloured red.

1. 1. Explain why the vertex corresponding to Ann must be joined to at least three of the others by arcs that are the same colour. [2]
   2. Now assume that Ann has met Bob, Caz and Del. Bob, Caz and Del may or may not have met one another. Explain why the graph must contain at least one triangle of arcs that are all the same colour. [2]