Trees

A tree is an acyclic, connected graph.

A forest is an acyclic graph.

A spanning tree of a graph $G$ is a spanning subgraph of $G$ which is a tree.

A spanning forest of a graph $G$ is a spanning subgraph of $G$ which is a forest.

A pendant vertex in a tree or graph is a vertex of degree 1.

A cut-edge in a graph is an edge so that, if you remove this edge, the graph becomes disconnnected.

Every tree $T$ has at least 2 pendant vertices.

Proof sketch: Consider a longest path in $T$. The endpoints of this path can have no neighbours outside the path, because the path is longest. They can have only one neighbour on the path, otherwise there would be a cycle. So they have degree 1.

Every tree $T$ with $n$ vertices has $n-1$ edges.

Sketch of proof by induction on $n$:

Basic step: $n=1$.

Inductive step: Pick $k\geq1$. Assume that any tree with $k$ vertices has $k-1$ edges.

Let $T$ be a tree with $k+1$ vertices. Remove a pendant vertex from $T$. The remaining graph is a tree with $k$ vertices, and we can apply induction.

Every connected graph has a spanning tree.

Every graph with a spanning tree is connected.

Every connected graph with $n$ vertices has at least $n-1$ edges.

A tree is a minimally connected graph.

If we remove any edge from a tree, then the remaining graph is disconnected.

A connected graph is a tree if and only if every edge is a cut-edge.

Rooted Trees

A directed tree is a directed graph for which the underlying undirected graph is a tree.

A directed tree is called a rooted tree if there is a unique vertex $r$, called the root so that $r$ has in-degree 1, and all other vertices has in-degree 1.

A leaf in a rooted tree is a vertex with outdegree zero.

A branch node is a vertex which is not a leaf.

Level $k$ of a rooted tree is the level containing all vertices at distance $k$ from the root.

If there is an edge $(u,v)$ in a rooted tree, then $v$ is a child of $u$, and $u$ is the parent of $v$.

An ancestor of a vertex $v$ is a vertex on the path from $r$ to $v$. Vertex $v$ is a descendant of $u$ if $u$ is an ancestor of $v$.

Two vertices with a common parent are called siblings.

The subtree at vertex $v$ is the subgraph induced by the root $v$ and all of its descendants.

A binary rooted tree is such that every vertex has at most two children. It is a complete binary tree if every branch node has exactly two children.