Complete graph properties

Questions asking about properties of complete graphs K_n, such as number of edges, spanning tree edges, Eulerian conditions, or Hamiltonian cycles.

7 questions · Easy -1.0

Sort by: Default | Easiest first | Hardest first

Draw the complete graph $K _ { 4 }$.
1. Find the total number of edges for the graph $K _ { 8 }$.
2. Give a reason why $K _ { 8 }$ is not Eulerian.
For the graph $K _ { n }$, state in terms of $n$ :
1. the total number of edges;
2. the number of edges in a minimum spanning tree;
3. the condition for $K _ { n }$ to be Eulerian;
4. the condition for the number of edges of a Hamiltonian cycle to be equal to the number of edges of an Eulerian cycle.

Draw the graph $\mathrm { K } _ { 5 }$ and state how you know that it is Eulerian.
By listing the arcs involved, give an example of a path in $\mathrm { K } _ { 5 }$. (Your path must include more than one arc.)
By listing the arcs involved, give an example of a cycle in $\mathrm { K } _ { 5 }$.

State the features of the graph that identify it as $K _ { 4 }$.
In $K _ { 4 }$, the Hamiltonian cycles $A B C D A , B C D A B , C D A B C$ and $D A B C D$ are usually regarded as being the same cycle. Find the number of distinct Hamiltonian cycles in
1. $\quad K _ { 4 }$,
2. $K _ { 5 }$,
3. $K _ { 10 }$.
In a weighted network, 8 possible routes must be placed in ascending order according to their lengths. The routes have the following lengths in kilometres: $$\begin{array} { l l l l l l l l } 27 & 25 & 29 & 32 & 19 & 24 & 17 & 26 \end{array}$$ Use a quick sort to obtain the sorted list, giving the state of the list after each comparison and indicating the pivot elements used.

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:
1. the number of edges in the graph;
2. the number of edges in a minimum spanning tree;
3. the number of edges in a Hamiltonian cycle.
1. Explain why the graph $\mathrm { K } _ { 7 }$ is Eulerian.
2. 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.

1. Write down the number of edges in a minimum spanning tree of $\mathbf { G }$.
2. Hence write down an inequality relating $m$ and $n$.
The graph $\mathbf { G }$ contains a Hamiltonian cycle. Write down the number of edges in this cycle.
In the case where $\mathbf { G }$ is Eulerian, draw a graph of $\mathbf { G }$ for which $m = 6$ and $n = 12$.

The complete graph $K_n$ has every one of its $n$ vertices connected to each of the other vertices by a single edge.
1. Find the total number of edges in the graph $K_5$. [1]
2. State the number of edges in a minimum spanning tree for the graph $K_5$. [1]
3. State the number of edges in a Hamiltonian cycle for the graph $K_5$. [1]
A simple graph $G$ has six vertices and nine edges, and $G$ is Eulerian. Draw a sketch to show a possible graph $G$. [2]

Draw the graph $K_5$ [1]
1. In the context of graph theory explain what is meant by 'semi-Eulerian'.
2. Draw two semi-Eulerian subgraphs of $K_5$, each having five vertices but with a different number of edges. [3]
Explain why a graph with exactly five vertices with vertex orders 1, 2, 2, 3 and 4 cannot be a tree. [2]