Graphs - Tutor Notes

Why use this interactivity?

The Graphs interactivity has been designed to provide an environment in which students can tackle a wide range of problems, and in which they can also pose and try to answer their own questions. There is enough flexibility that questions on a range of topics in the area of graphs and networks can be investigated.

One of the attractive features of this area of mathematics is that many interesting questions can be asked and answered without needing to know much about the theory. This makes it ideally suited for problem solving for a wide variety of students (of a range of ages and levels of mathematical experience).

Possible approaches

Students could be given one or more questions or starting points for exploration, and could be encouraged to use the interactivity to develop their own examples to help with making conjectures and finding answers.

Here are some examples of possible questions:

• Let G be a graph with vertices x₁, x₂, …, x_n, with degrees d(x₁), d(x₂), …, d(x_n) respectively. Find (with proof) an expression for d(x₁) + d(x₂) + … + d(x_n) in terms of e(G).
• If a graph is not connected, must its complement be connected?
• Can each vertex of a finite graph have a different degree?
• For each of the following statements, decide whether it is true, and give a proof or counterexample as appropriate:
  • Let G be a graph whose edge set can be partitioned into cycles. Then every vertex has even degree.
  • Let G be a graph where every vertex has even degree. Then its edge set can be partitioned into cycles.
  • Let G be a connected graph. Is there necessarily a vertex so that G - x (that is, the graph with the vertex and its adjoining edges removed) is connected? Are there necessarily two distinct vertices x and y so that both G - x and G - y are connected? Are there necessarily three vertices x, y and z so that G - x, G - y and G - z are all connected? And so on!
• Concentrate just on planar graphs. Can you find a relationship between the numbers of vertices, edges and faces? Can you prove that your relationship always holds?
• Can you find an easy way to tell whether or not a graph has an Eulerian circuit? Can you justify why your criterion works?
• Concentrate just on bipartite graphs. Can you find a good way to tell whether or not there is a matching in a bipartite graph? Can you justify why your condition is both necessary and sufficient?

Related problems

There are several problems on NRICH that could be tackled using the interactivity to generate examples. These include Tree Graphs, Maximum Flow and Pattern of Islands.