Trees

Determine whether an undirected tree is planar, Eulerian, semi-Eulerian, Hamiltonian? Find its chromatic number.

Find a formula relating the number of vertices and edges for a forest of $k$ undirected trees.

Prove that in an undirected tree $\mathfrak {T}=(V, E)$ containing at least one edge, the number of leaves equals $2+\sum_{v \in V_{2}}(\operatorname {deg} v-2)$, where $V_{2}$ is the set of non-leaf vertices.

Prove that if in a connected undirected graph the number of vertices equals the number of edges, then one of the edges can be discarded so that the graph becomes a tree.

Prove that in an undirected tree there exists a vertex through which all maximal simple paths pass.

Prove Lemma 76 on page 221.

Lemma 76: Suppose an arbitrary vertex $v \in V$ is chosen in an undirected tree $\mathfrak {T}=(V, E)$. For each vertex $u$ denote by $n(u)$ the minimal length of a path from $v$ to $u$. For each undirected edge $(u, w)$ define its direction from $u$ to $w$ if $n(u)<n(w)$. Then the resulting graph is a directed tree with root $v$.

Prove Theorem 77 on page 223 in the reverse direction.

Theorem 77: Definitions 93 (p. 221) and 94 (p. 222) of a directed tree are equivalent.

Definition 93 (Directed tree): a directed graph $\mathfrak {T}=(V, E)$ is called a (directed) tree if 1) it has exactly one source $r \in V$, called the root of the tree; 2) exactly one edge leads into each of the remaining vertices; 3) every vertex is reachable from the root.

Definition 94 (Directed tree, inductive definition): a directed graph is a tree in the following cases. 1) Any graph $\mathfrak {T}_{0}=(V, E)$ with a single vertex $V=\left\{ v\right\}$ and empty edge set $E=\emptyset$ is a tree; the vertex $v$ is called the root of this tree. 2) Suppose the graphs $\mathfrak {T}_{1}=\left(V_{1}, E_{1}\right), \ldots , \mathfrak {T}_{k}=\left(V_{k}, E_{k}\right)$ are trees with roots $r_{1} \in V_{1}, \ldots , r_{k} \in V_{k}$ respectively, the vertex sets $V_{i}$, $i=1, \ldots , k$, are pairwise disjoint, and $r_{0}$ is a new vertex, $r_{0} \notin V_{i}$, $i=1, \ldots , k$. Then the following graph $\mathfrak {T}=(V, E)$ is also a tree with root $r_{0}$: $V=\left\{ r_{0}\right\} \cup \bigcup_{i=1}^{k} V_{i}$, $E=\left\{ (r_{0}, r_{i}): i=1, \ldots , k\right\} \cup \bigcup_{i=1}^{k} E_{i}$.

"The reverse direction" means: if a graph $\mathfrak {T}$ satisfies Definition 94, then conditions 1)-3) of Definition 93 hold for it, proved by induction on the construction from Definition 94.

Let $\mathfrak {T}=(V, E)$ be a directed tree with root $v_{0} \in V$. For each vertex $v \in V$ define the subgraph $\mathfrak {T}_{v}=\left(V_{v}, E_{v}\right)$ as follows: $V_{v}$ is the set of vertices reachable from $v$ in $\mathfrak {T}$, and $E_{v}$ is the set of edges from $E$ both of whose endpoints belong to $V_{v}$. Prove that

Let $\leqslant$ be a partial order relation on a finite set $V$ possessing the following two properties:

Let $\mathfrak {T}=(V, E)$ be a directed tree, and let $x \leqslant y$ mean that vertex $y$ is reachable from vertex $x$. Prove that $\leqslant$ is a non-strict partial order relation on $V$ satisfying properties (a) and (b) from the previous problem.

Let $\mathfrak {G}=(V, E)$ be a directed graph with at least two vertices. Prove that the graph $\mathfrak {G}$ is a (directed) tree if and only if $\mathfrak {G}$ has no cycles, has a single source $r$, and into each of the remaining vertices $v \in V \backslash \left\{ r\right\}$ exactly one edge leads.

For the vertex set $V=\left\{ v_{1}, \ldots , v_{n}\right\}$, determine how many undirected trees exist in which

Suppose the root of a directed tree $\mathfrak {T}$ has five sons, and each of the remaining internal vertices has three or four sons, where the number of vertices with three sons is twice the number of vertices with four. How many vertices and edges are there in total in $\mathfrak {T}$, given that its number of leaves equals $26$?

Let $\mathfrak {F}=\left(\mathfrak {T}_{1}, \ldots , \mathfrak {T}_{n}\right)$ be a forest of trees. Prove that from the sequence $P=\left(\operatorname {PRF}\left(\mathfrak {T}_{1}\right), \ldots , \operatorname {PRF}\left(\mathfrak {T}_{k}\right)\right)$ one can uniquely reconstruct the forest $\mathfrak {F}$. Prove the analogous statement for the suffix traversal.

Prove by induction that in every binary tree the number $n$ of vertices with two sons is one less than the number $\ell$ of leaves.

How many leaves and vertices are there in a complete binary tree of height $h$?

Construct a tree and an acyclic directed graph representing the following arithmetic formula

How many vertices were saved?

Construct a tree representing the following logical formula

For the resulting tree, construct the prefix, suffix, and infix traversals (for negation vertices with a single son, count it as the right one).