Introduction to graph theory/Lecture 2

Introduction

It is useful, and indeed vital, to have the collection of definitions that were doled out in the last lecture. Nevertheless, in order to get a feel for what these definitions mean, one must actually get one's hands dirty. Today we start investigating the consequences of these definitions. We start by investigating graphs with no cycles.

What is a forest?

A graph is said to be a forest if it contains no cycles (this property is also called being acyclic). A sample forest from the Kevin Bacon Graph is given below. The vertices have been placed in order to give some idea as to the reason for the name forest.

It is time for the second theorem of the course. To reiterate what was said in the first lecture, proofs to the theorems will not be given in the main body of the lecture. Instead, there will be a "roadmap" of the proof, for the student to fill in himself. At the end of each theorem there is a link to a proof page.

Theorem 2: A graph is a forest if and only if for every pair of distinct vertices $u,v$, there is at most one $u,v$-path.

Proof Roadmap:

• Suppose you have a graph $G$ which is not a forest.
  • What must G contain?
  • Take an example of the thing that is in all non-forest graphs.
  • Choose two vertices from your example, and try to find two paths between them.
• Suppose you have a graph $G$ with two vertices $u,v$ with two $u,v$-paths.
  • By drawing a picture, allowing your paths to cross over each other many times, attempt to see why this graph cannot be a forest.
  • Now formalise this argument, making certain that what you construct uses no vertex more than once.

QED (Full Proof)

If a forest is connected, it is called a tree. This naming may seem a little counterintuitive, but note that forests consist of a collection of trees. If deforestation were to continue to the extent that Sherwood Forest was reduced to having only one plant in it, then the forest may well be renamed Sherwood Tree. The previous theorem has the following easy corollary.

Corollary 3: A graph is a tree if and only if for every pair of distinct vertices $u,v$, there is exactly one $u,v$-path.

Proof Roadmap:

• Suppose you have a graph $G$ which is not a forest.
  • Use Theorem 2 to show that there is some pair of vertices $u,v$ for which there is not exactly one $u,v$-path.
• Suppose you have a graph $G$ which is a forest, but is not a tree.
  • What property must $G$ fail to have?
  • Looking back at the definition in the previous lecture, if necessary, show that this means that there is some pair of vertices $u,v$ for which there is not exactly one $u,v$-path.
• Now suppose you have a graph $G$ which is a tree.
  • Use Theorem 2 and the same definition to show that for every pair of vertices $u,v$, there is exactly one $u,v$-path.

QED (Full Proof)

As a tree is such a useful concept, we will give (in the following theorem) two alternative characterisations of trees.

Theorem 4: For a graph $G$, the following are equivalent:

• $G$ is a tree
• $G$ is a minimal connected graph, in the sense that the removal of any edge will leave a disconnected graph.
• $G$ is a maximal acyclic graph, in the sense that the addition of any missing edge will create a cycle.

Proof Roadmap

• Suppose $G$ is a tree, and let $uv$ be an edge not in $G$.
  • Use Corollary 3 to show that adding $uv$ to $G$ will create a cycle.
• Suppose $G$ is a tree, and let $uv$ be an edge of $G$.
  • Find two vertices such that the graph $G-uv$ can have no path between them.
• Suppose $G$ is a minimal connected graph, but is not a tree.
  • From the definition of a tree, what else does this mean that G is not?
  • Therefore, what must $G$ contain?
  • Find an edge you can remove from $G$ without disconnecting the graph.
• Suppose $G$ is a maximal acyclic graph, but is not a tree.
  • Since acyclic graphs and forests are the same thing, what property does $G$ not have?
  • Using this, show that there are two non-adjacent vertices which can be joined without creating a cycle.

QED (Full Proof)

We will need one more theorem about trees here. It is not immediately obvious that all trees have one fewer edge than vertex. The proof, as you shall see, is easy.

Theorem 5: A tree of order $n$ has $n-1$ edges.

Proof Roadmap

• Prove this by induction on $n$.
• Prove this first (by experimenting) for $n=1,2,3$. Find all trees for these values of $n$.
• Now let $T$ be a tree of k vertices, and suppose it is true for all $n<k$. Remove an edge from T.
  • By Theorem 4, the new graph cannot be connected. Can it have three or more components?
  • What must each component be?
  • How many vertices are there in total in the components?
  • Therefore, using the induction statement, how many edges must there be?

QED (Full Proof)

Conclusion

Resource type: this resource contains a lecture or lecture notes.