Simple and connected definitions

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

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

1. A graph is simple if it contains neither loops nor multiple arcs, ie none of the following: \includegraphics[max width=\textwidth, alt={}, center]{a09472cd-8f65-4cca-9683-c386053e66aa-2_81_134_219_1683}
   or \includegraphics[max width=\textwidth, alt={}, center]{a09472cd-8f65-4cca-9683-c386053e66aa-2_79_589_301_328} In an examination question, students were asked to describe in words when a graph is simple. Mark the following responses as right or wrong, giving reasons for your decisions if you mark them wrong.
   1. A graph is simple if there are no loops and if two nodes are connected by a single arc.
   2. A graph is simple if there are no loops and no two nodes are connected by more than one arc.
   3. A graph is simple if there are no loops and two arcs do not have the same ends.
   4. A graph is simple if there are no loops and there is at most one route from one node to another.
2. The following picture represents a two-way switch \includegraphics[max width=\textwidth, alt={}, center]{a09472cd-8f65-4cca-9683-c386053e66aa-2_149_138_932_1119} It can either be in the up state \includegraphics[max width=\textwidth, alt={}, center]{a09472cd-8f65-4cca-9683-c386053e66aa-2_104_104_1128_790}
   or in the down state • or in the down state . Two switches can be used to construct a circuit in which changing the state of either switch changes the state of a lamp. \includegraphics[max width=\textwidth, alt={}, center]{a09472cd-8f65-4cca-9683-c386053e66aa-2_309_543_1448_762} Georgios tries to connect together three two-way switches so that changing the state of any switch changes the state of the lamp. His circuit is shown below. The switches have been labelled 1,2 and 3. \includegraphics[max width=\textwidth, alt={}, center]{a09472cd-8f65-4cca-9683-c386053e66aa-2_496_547_1946_760}
   1. List the possible combination of switch states and determine whether the lamp is on or off for each of them.
   2. Say whether or not Georgios has achieved his objective, justifying your answer.
3. Use a truth table to show that \(( \mathrm { A } \wedge ( \mathrm { B } \vee \mathrm { C } ) ) \vee \sim ( \sim \mathrm { A } \vee ( \mathrm { B } \wedge \mathrm { C } ) ) \Leftrightarrow \mathrm { A }\).

2. A simply connected graph is a connected graph in which any two vertices are directly connected by at most one arc and no vertex is directly connected to itself.

1. Given that a simply connected graph has exactly four vertices,
   1. write down the minimum number of arcs it can have,
   2. write down the maximum number of arcs it can have.
2. 1. Draw a simply connected graph that has exactly four vertices and exactly five arcs.
   2. State, with justification, whether your graph is Eulerian, semi-Eulerian or neither.
3. By considering the orders of the vertices, explain why there is only one simply connected graph with exactly four vertices and exactly five arcs.

7

1. A simple connected graph has 4 edges and \(m\) vertices. State the possible values of \(m\).
2. A simple connected graph has \(n\) edges and 4 vertices. State the possible values of \(n\).
3. A simple connected graph, \(G\), has 5 vertices and is Eulerian but not Hamiltonian. Draw a possible graph \(G\).
   [0pt] [2 marks]

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. What is the minimum number of arcs that a simply connected graph with six vertices can have? Draw an example of such a graph. [2]
2. What is the maximum number of arcs that a simply connected graph with six vertices can have? Draw an example of such a graph. [2]
3. What is the maximum number of arcs that a simply connected Eulerian graph with six vertices can have? Explain your reasoning. [2]
4. State how you know that the graph below is semi-Eulerian and write down a semi-Eulerian trail for the graph. [2]

\includegraphics{figure_2}