Vertex degree sequences

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

3. (a) Draw a graph with 6 vertices, each of degree 1 .
(b) Draw two graphs with 6 vertices, each of degree 2 such that:

1. the graph is connected,
2. the graph is not connected. A simple connected graph has 5 vertices each of degree \(x\).
   (c) Find the possible values of \(x\) and explain your answer.
   (d) For each value of \(x\) you found in part (c) draw a possible graph.

6 A connected graph is semi-Eulerian if exactly two of its vertices are of odd degree.

1. A graph is drawn with 4 vertices and 7 edges. What is the sum of the degrees of the vertices?
2. Draw a simple semi-Eulerian graph with exactly 5 vertices and 5 edges, in which exactly one of the vertices has degree 4 .
3. Draw a simple semi-Eulerian graph with exactly 5 vertices that is also a tree.
4. A simple graph has 6 vertices. The graph has two vertices of degree 5 . Explain why the graph can have no vertex of degree 1.