Finding variable values in degree sequences

4. (a) Explain why it is not possible to draw a graph with exactly 5 nodes with orders \(1,3,4,4\) and 5 A connected graph has exactly 5 nodes and contains 18 arcs. The orders of the 5 nodes are \(2 ^ { 2 x } - 1,2 ^ { x } , x + 1,2 ^ { x + 1 } - 3\) and \(11 - x\).
(b) (i) Calculate X .
(ii) State whether the graph is Eulerian, semi-Eulerian or neither. You must justify your answer.
(c) Draw a graph which satisfies all of the following conditions:

• The graph has exactly 5 nodes.
• The nodes have orders 2, 2, 4, 4 and 4
• The graph is not Eulerian.

7 A simply connected graph has 6 vertices and 10 arcs.

1. What is the maximum vertex degree? You are now given that the graph is also Eulerian.
2. Explaining your reasoning carefully, show that exactly two of the vertices have degree 2 .
3. Prove that the vertices of degree 2 cannot be adjacent to one another.
4. Use Kuratowski's theorem to show that the graph is planar.
5. Show that it is possible to make a non-planar graph by the addition of one more arc. A digraph is created from a simply connected graph with 6 vertices and \(10 \operatorname { arcs }\) by making each arc into a single directed arc.
6. What can be deduced about the indegrees and outdegrees?
7. If a Hamiltonian cycle exists on the digraph, what can be deduced about the indegrees and outdegrees? \section*{OCR} \section*{Oxford Cambridge and RSA}

8 In this question you may use the fact that any simple graph must have an even number of vertices of odd degree.

1. A simple graph has five vertices and their degrees are $$x , x + 1 , x + 1 , x + 2 \text { and } x + 3$$
   1. Show that \(x\) must be odd.
   2. Find the value of \(x\) and draw a graph with vertices having the given degrees.
2. A simple graph has 10 vertices.
   1. State the minimum possible degree and maximum possible degree of a vertex.
   2. Show that the degrees of the vertices cannot all be different.
      □
      □

A simple connected graph has six vertices.

1. One vertex has degree \(x\). State the greatest and least possible values of \(x\). [2 marks]
2. The six vertices have degrees $$x - 2, \quad x - 2, \quad x, \quad 2x - 4, \quad 2x - 4, \quad 4x - 12$$ Find the value of \(x\), justifying your answer. [2 marks]