MA010 Graph Theory (an online guide)

Lecture 4: Basics of trees


  • Definition and basic properties of trees
    tree is a connected acyclic graph; basic equivalent characterizations - minimal connected, maximal acyclic, path uniqueness, number of edges
  • Rooted trees and isomorhpism testing
    rooted, and planted (i.e. rooted plus ordered) trees, planted tree coding and decoding, tree center, isomorphism testing for trees via coding
  • Spanning trees
    definition, and enumeration of spanning trees in a graph


The main goal of this lecture is to survey (and prove) some basic theoretical properties of trees, i.e. the simplest graphs from a structural point of view. The numerous presented simple proofs, moreover, show "in action" several powerful proof methods and tools of discrete mathematics. Additionally, a nice and fast method of testing isomorphism between trees is outlined.

[BOOK]Course book  [Invitation to Discrete Mathematics (by Jiří Matoušek, Jaroslav Nešetřil)]:

Study the whole Sections 5.1, 5.2, and a few words from 5.3 and Chapter 8. Specifically, Section 8.5 gives a (difficult) proof of the determinant formula for the number of spanning trees of a graph.

Unlike in the book, we are pure computer scientists, and thus we depict rooted trees with the root on the top.