Trees

Determine whether an undirected tree is a planar, Eulerian, semi-Eulerian, Hamiltonian graph. 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 leaf vertices equals $2+\sum_{v \in V_{2}}(\operatorname {deg} v-2)$, where $V_{2}$ is the set of non-leaf vertices.

Prove that if an undirected tree has exactly two leaf vertices, then it is a "line".

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 afterwards the graph becomes a tree.

A center of an undirected graph $\mathfrak {G}$ is a vertex $v$ for which the length of the longest path from it to the other vertices is minimal. Prove that in a tree

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

Let $\mathfrak {T}=(V, E)$ be an undirected tree, $v \in V$ an arbitrary vertex of it. For each edge $(u, w) \in E$ choose the orientation from $u$ to $w$ if the distance from $v$ to $u$ is less than from $v$ to $w$. Prove that the resulting directed graph will be a directed tree with root $v$.

Prove the following statement in two ways: if an undirected tree $\mathfrak {T}=(V, E)$ has a vertex $v$ of degree $d>1$, then it has at least $d$ leaf vertices.

For the set of vertices $V=\left\{ v_{1}, \ldots , v_{n}\right\}$ determine how many undirected trees there are in which

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 of $E$ both of whose ends belong to $V_{v}$. Prove that

Give an example of a directed graph for which the first two conditions from the definition of a tree hold, but which is not a tree.

A certain rumor spread as follows: its source called three of his friends, each of them passed on the rumor by phone to four of their friends, and each of them, in turn, passed it on to five of their friends. Determine how many people learned the rumor, given that none of them received more than one call and no one called the source of the rumor. Find how many calls were made in total.

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 the vertex $y$ is reachable from the vertex $x$. Prove that $\leqslant$ is a non-strict partial order relation on $V$ satisfying properties (а) and (б) 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 exactly one edge leads into each of the other vertices $v \in V \backslash \left\{ r\right\}$.

Let $\mathfrak {G}=(V, E)$ be a directed graph. Prove that $\mathfrak {G}$ is a (directed) tree if and only if $\mathfrak {G}$ has a vertex $r$ (the root) such that exactly one path leads from $r$ to any vertex $v$.

Let the root of a directed tree $\mathfrak {T}$ have five children, and let each of the other internal vertices have three or four children, with the number of vertices with three children being twice the number of vertices with four. How many vertices and edges are there in total in $\mathfrak {T}$, given that the number of its leaves equals 26?

Let the root of a directed tree $\mathfrak {T}$ have three children, and let each of the other internal vertices have two or four children, with the number of vertices with two children being half the number of vertices with four. How many vertices are there in total in $\mathfrak {T}$, given that the number of its leaves equals 38?

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)$ the forest $\mathfrak {F}$ can be uniquely reconstructed. Prove the analogous statement for the postfix traversal.

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

Find the number of leaves and vertices in a complete binary tree of height $h$.

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

How many vertices could be saved?

Construct a tree representing the following logical formula

For the resulting tree construct the prefix, postfix, and infix traversals (for vertices with negations regard the single child as the right one).

Determine the prefix, postfix, and infix traversals of the tree $\mathfrak {T}_{1}$ depicted in fig. 12 on the next page, assuming that the edges leaving a single vertex are numbered from left to right.

Fig. 12: The tree \mathfrak {T}_{1}.

Determine the prefix and postfix traversals of the tree $\mathfrak {T}_{2}$ depicted in fig. 13 on the opposite page, assuming that the edges leaving a single vertex are numbered from left to right.

Fig. 13: The tree \mathfrak {T}_{2}.

Let $(x, z, u, v, /,-, \times , y, z,-, x, y,+, \times ,+)$ be the postfix traversal of the tree of an arithmetic formula built from the variables $x, y, z, u, v$ and the operation signs,,$+- \times , /$. Reconstruct this tree and the formula.