1 There are six non-isomorphic trees with exactly six vertices.
A student has drawn the diagram below showing six trees each with exactly six vertices. However, two of the trees that the student has drawn are isomorphic.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{6f64abca-108c-4b81-8ccf-124dfd9cc2f6-2_222_243_388_246}
\captionsetup{labelformat=empty}
\caption{A}
\end{figure}
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{6f64abca-108c-4b81-8ccf-124dfd9cc2f6-2_214_240_392_635}
\captionsetup{labelformat=empty}
\caption{B}
\end{figure}
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{6f64abca-108c-4b81-8ccf-124dfd9cc2f6-2_214_241_392_1023}
\captionsetup{labelformat=empty}
\caption{C}
\end{figure}
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{6f64abca-108c-4b81-8ccf-124dfd9cc2f6-2_218_246_758_246}
\captionsetup{labelformat=empty}
\caption{D}
\end{figure}
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{6f64abca-108c-4b81-8ccf-124dfd9cc2f6-2_216_243_760_632}
\captionsetup{labelformat=empty}
\caption{E}
\end{figure}
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{6f64abca-108c-4b81-8ccf-124dfd9cc2f6-2_214_241_762_1023}
\captionsetup{labelformat=empty}
\caption{F}
\end{figure}
- Identify which two of these trees are isomorphic.
- Draw an example of the missing tree.
Graph G has exactly six vertices.
The degree sequence of G is \(1,1,1,3,3,3\). - Without using a sketch, calculate the number of edges in graph G.
- Explain how the result from part (c) shows that graph G is not a tree.
In a simple graph with six vertices each vertex degree must be one of the values \(0,1,2,3,4\) or 5 .
- Use the pigeonhole principle to show that in a simple graph with six vertices there must be at least two vertices with the same vertex degree.