Outline

• 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

Goals

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.

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.

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