Skip to main content\( \newcommand{\identity}{\mathrm{id}}
\newcommand{\notdivide}{{\not{\mid}}}
\newcommand{\notsubset}{\not\subset}
\newcommand{\lcm}{\operatorname{lcm}}
\newcommand{\gf}{\operatorname{GF}}
\newcommand{\inn}{\operatorname{Inn}}
\newcommand{\aut}{\operatorname{Aut}}
\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\cis}{\operatorname{cis}}
\newcommand{\chr}{\operatorname{char}}
\newcommand{\Null}{\operatorname{Null}}
\def\Z{\mathbb Z}
\def\R{\mathbb R}
\def\Q{\mathbb Q}
\def\N{\mathbb N}
\def\C{\mathbb C}
\def\W{\mathbb W}
\def\ba{{\mathbf{a}}}
\def\bb{\mathbf{b}}
\def\bh{{\mathbf{h}}}
\def\bu{{\mathbf{u}}}
\def\bv{{\mathbf{v}}}
\def\bw{{\mathbf{w}}}
\def\bx{{\mathbf{x}}}
\def\by{\mathbf{y}}
\def\bone{{\mathbf{1}}}
\def\bzero{\mathbf{0}}
\def\var{{\mbox{var}}}
\def\P{{\mathbb{P}}}
\def\E{{\mathbb{E}}}
\def\cA{{\mathcal{A}}}
\def\cB{{\mathcal{B}}}
\def\cC{{\mathcal{C}}}
\def\cP{\mathcal P}
\def\cN{\mathcal N}
\def\cE{\mathcal E}
\def\cO{\mathcal O}
\def\cF{\mathcal F}
\def\cX{\mathcal X}
\def\nimsum{\, \oplus \,}
\def\mex{{\mathrm{mex}}}
\newcommand{\pile}[1]{\bullet{#1}}
\def\g{g}
\def\kin{k^{\mathrm{in}}}
\def\kout{k^{\mathrm{out}}}
\newcommand{\indeg}[1]{k^{\mathrm{in}}_{#1}}
\newcommand{\outdeg}[1]{k^{\mathrm{out}}_{#1}}
\tikzset{->-/.style={decoration={
markings,
mark=at position .5 with {\arrow{latex}}},postaction={decorate}}}
\newcommand{\nimbleboard}[1]{
\begin{scope}[shift={(.25, .4)}]
\draw (0,-.3) -- (#1,-.3) -- (#1+.45, .7) -- (#1+.45, 1);
\draw (0,0) -- (#1,0);
\draw (.45,1) -- (#1+.45,1);
\foreach \i in {0, ..., #1} {
\draw (\i, -.3) -- (\i, 0) -- (\i+.45,1);
}
\foreach \i in {1, ..., #1} {
\node[style={font=\sffamily\scriptsize}] at (\i - .5, -.15) {\i};
}
\end{scope}
}
\newcommand{\coin}[1]{
\begin{scope}[shift={#1}]
\draw[color=white, fill=white] (-.4, 0) -- (-.4, -.1) -- (.4,-.1) -- (.4,0) -- cycle;
\draw[thick, fill=white] (0,0) ellipse (0.4 and 0.10);
\draw[thick, fill=white] (.4,-.1) arc (0:-180:0.4 and 0.10);
\draw[thick] (0.4,0) -- (0.4, -.1);
\draw[thick] (-0.4,0) -- (-0.4, -.1);
\end{scope}
}
\newcommand{\bean}[2]{
\begin{scope}[shift={#1}, rotate={#2}]
\draw [very thick, fill=gray!50] plot [smooth cycle] coordinates {(-.2,0) (-.175, .07) (-.1,.1) (0,.075) (.1,.1) (.175, .07) (.2,0) (.15, -.07) (0,-.1) (-.15, -.07)};
\end{scope}
}
\newcommand{\heap}[2]{
\begin{scope}[shift={#1}]
\draw[very thick] (0,0) circle ({#2});
\end{scope}
}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\)
Chapter 12 Trees
Exercises Practice Problems
1. Trees on 4 Vertices.
Draw all non-isomorphic trees on 4 vertices
2. Trees on 5 Vertices.
Draw all non-isomorphic trees on 5 vertices
3. Leaves on Trees.
More generally, consider the set of trees on \(n \geq 3\) vertices. Which tree has the fewest leaves? Which tree has the most leaves? Draw these trees and state how many leaves each has.
4. A Tree Has At Least 2 Leaves.
In this problem, you will give another proof that a tree on \(n \geq 3\) has at least two leaves (recall that a leaf is a vertex with degree equal 1). Let \(G\) be a tree on \(n\geq 3\) vertices. Let \(S\) be the set of all paths from one vertex to another on \(G\text{.}\) Among all the paths in \(S\text{,}\) let \(P\) be a path with the most edges.
How does this path \(P\) help us to find two leaves?
5. Definitions for a Tree.
Here is a theorem that gives four different ways to describe a tree.
Theorem: The following statements are equivalent for a graph \(G=(V,E)\) on \(n\) vertices
\(G\) is connected and acyclic
\(G\) is connected and \(|E|=n-1\)
\(G\) is acyclic and \(|E|=n-1\)
There is a unique path between each pair of vertices in \(G\)
\(G\) is connected but deleting any edge disconnects the graph.
We will focus on (d) \(\Rightarrow\) (a) and the equivalence (a) \(\Leftrightarrow\) (e).
Prove that (d) \(\Rightarrow\) (a) using a proof by contradiction. Assuming that (d) holds, why must \(G\) be connected? Why must \(G\) be acyclic?
Prove that (a) \(\Rightarrow\) (e) using a proof by contradiction. Assume that (a) holds, but there is an edge \(e\) such that the graph \(G-e\) obtained by removing \(e\) is connected. Why does this lead to a contradiction?
Prove that (e) \(\Rightarrow\) (a) by proving the contrapositive statement "not (a) \(\Rightarrow\) not (e)."