Easy -1.2 This question tests basic recall of graph theory definitions and properties with minimal problem-solving. Parts (a) and (b) require direct application of standard formulas and definitions (edges in K_n, MST properties, Eulerian conditions), while part (c) asks for a simple construction. All are routine textbook exercises requiring no novel insight or extended reasoning.
In the complete graph \(\mathrm { K } _ { 7 }\), every one of the 7 vertices is connected to each of the other 6 vertices by a single edge.
Find or write down:
the number of edges in the graph;
the number of edges in a minimum spanning tree;
the number of edges in a Hamiltonian cycle.
Explain why the graph \(\mathrm { K } _ { 7 }\) is Eulerian.
Write down the condition for \(\mathrm { K } _ { n }\) to be Eulerian.
A connected graph has 6 vertices and 10 edges.
Draw an example of such a graph which is Eulerian.
4
\begin{enumerate}[label=(\alph*)]
\item In the complete graph $\mathrm { K } _ { 7 }$, every one of the 7 vertices is connected to each of the other 6 vertices by a single edge.
Find or write down:
\begin{enumerate}[label=(\roman*)]
\item the number of edges in the graph;
\item the number of edges in a minimum spanning tree;
\item the number of edges in a Hamiltonian cycle.
\end{enumerate}\item \begin{enumerate}[label=(\roman*)]
\item Explain why the graph $\mathrm { K } _ { 7 }$ is Eulerian.
\item Write down the condition for $\mathrm { K } _ { n }$ to be Eulerian.
\end{enumerate}\item A connected graph has 6 vertices and 10 edges.
Draw an example of such a graph which is Eulerian.
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2005 Q4 [7]}}