SmarterEd

Aussie Maths & Science Teachers: Save your time with SmarterEd

Networks, GEN2 2023 VCAA 12

A country has five states, \(A, B, C, D\) and \(E\).

A graph can be drawn with vertices to represent each of the states.

Edges represent a border shared between two states.

  1. What is the sum of the degrees of the vertices of the graph above?  (1 mark)

  2. Euler's formula, \(v+f=e+2\), holds for this graph.

    1. Complete the formula by writing the appropriate numbers in the boxes provided below.  (1 mark)

    2. Complete the sentence by writing the appropriate word in the space provided below.  (1 mark)

    3. Euler’s formula holds for this graph because the graph is connected and ______________.
  3. The diagram below shows the position of state \(A\) on a map of this country.
  4. The four other states are indicated on the diagram as 1, 2, 3 and 4.
     

  1. Use the information in the graph above to complete the table below. Match the state \((B, C, D\) and \(E)\) with the corresponding state number \((1,2,3\) and 4\()\) given in the map above.  (1 mark)

\begin{array} {|c|c|}
\hline
\rule{0pt}{2.5ex} \quad \quad \textbf{State} \quad \quad \rule[-1ex]{0pt}{0pt} & \textbf{State Number} \\
\hline
\rule{0pt}{2.5ex} B \rule[-1ex]{0pt}{0pt} &\\
\hline
\rule{0pt}{2.5ex} C \rule[-1ex]{0pt}{0pt} & \\
\hline
\rule{0pt}{2.5ex} D \rule[-1ex]{0pt}{0pt} & \\
\hline
\rule{0pt}{2.5ex} E \rule[-1ex]{0pt}{0pt} &  \\
\hline
\end{array}

Show Answers Only

a.    \(\text{Sum of degrees}\ = 2+3+4+3+2 = 14\)
 

b.i.   \(\text{Vertices = 5,  Faces = 4,  Edges = 7}\)

\(\Rightarrow 5 + 4 = 7 + 2\)
 

b.ii.     \(\text{Planar}\)
 

c.   

\begin{array} {|c|c|}
\hline
\rule{0pt}{2.5ex} \quad \quad \textbf{State} \quad \quad \rule[-1ex]{0pt}{0pt} & \textbf{State Number} \\
\hline
\rule{0pt}{2.5ex} B \rule[-1ex]{0pt}{0pt} & 3\\
\hline
\rule{0pt}{2.5ex} C \rule[-1ex]{0pt}{0pt} & 2 \\
\hline
\rule{0pt}{2.5ex} D \rule[-1ex]{0pt}{0pt} & 4 \\
\hline
\rule{0pt}{2.5ex} E \rule[-1ex]{0pt}{0pt} &  1 \\
\hline
\end{array}

Show Worked Solution

a.    \(\text{Sum of degrees}\ = 2+3+4+3+2 = 14\)
 

b.i.   \(\text{Vertices = 5,  Faces = 4,  Edges = 7}\)

\(\Rightarrow 5 + 4 = 7 + 2\)
 

b.ii.     \(\text{Planar}\)
 

c.   

\begin{array} {|c|c|}
\hline
\rule{0pt}{2.5ex} \quad \quad \textbf{State} \quad \quad \rule[-1ex]{0pt}{0pt} & \textbf{State Number} \\
\hline
\rule{0pt}{2.5ex} B \rule[-1ex]{0pt}{0pt} & 3\\
\hline
\rule{0pt}{2.5ex} C \rule[-1ex]{0pt}{0pt} & 2 \\
\hline
\rule{0pt}{2.5ex} D \rule[-1ex]{0pt}{0pt} & 4 \\
\hline
\rule{0pt}{2.5ex} E \rule[-1ex]{0pt}{0pt} &  1 \\
\hline
\end{array}

Networks, GEN1 2023 VCAA 33 MC

Consider the following graph.
 

How many of the following five statements are true?

  • The graph is a tree.
  • The graph is connected.
  • The graph contains a path.
  • The graph contains a cycle.
  • The sum of the degrees of the vertices is eight.
  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
Show Answers Only

\(D\)

Show Worked Solution

The graph is a tree (any two vertices are connected by one edge).  \(\checkmark\)

The graph is connected.  \(\checkmark\)

The graph contains a path.  \(\checkmark\)

The graph contains a cycle.  \(\cross\)

The sum of the degrees of the vertices is eight.  \(\checkmark\)

\(\Rightarrow D\)

NETWORKS, FUR2 2018 VCAA 2

In one area of the town of Zenith, a postal worker delivers mail to 10 houses labelled as vertices `A` to `J` on the graph below.
 

  1. Which one of the vertices on the graph has degree 4?  (1 mark)

For this graph, an Eulerian trail does not currently exist.

  1. For an Eulerian trail to exist, what is the minimum number of extra edges that the graph would require.  (1 mark)
  2. The postal worker has delivered the mail at `F` and will continue her deliveries by following a Hamiltonian path from `F`.

     

    Draw in a possible Hamiltonian path for the postal worker on the diagram below.  (1 mark)

 

Show Answers Only
  1. `text(Vertex)\ F`
  2. `2`
  3.  `text(See Worked Solutions)`
Show Worked Solution

a.   `text(Vertex)\ F`
 

b. `text(Eulerian trail)\ =>\ text(all edges used exactly once.)`

`text(6 vertices are odd)`

`=> 2\ text(extra edges could create graph with only 2)`

`text(odd vertices)`

`:.\ text(Minimum of 2 extra edges.)`
 

c.  `text{One example (of a number) beginning at)\ F:}`
 


 

`text{(Note: path should not return to}\ F text{)}`

NETWORKS, FUR1 2017 VCAA 2 MC

Two graphs, labelled Graph 1 and Graph 2, are shown below.
 

 
The sum of the degrees of the vertices of Graph 1 is

  1. two less than the sum of the degrees of the vertices of Graph 2.
  2. one less than the sum of the degrees of the vertices of Graph 2.
  3. equal to the sum of the degrees of the vertices of Graph 2.
  4. one more than the sum of the degrees of the vertices of Graph 2.
  5. two more than the sum of the degrees of the vertices of Graph 2.
Show Answers Only

`C`

Show Worked Solution

`text(Graph 1)`

`∑\ text(degrees)\ = 3 + 3 + 3 + 3 = 12`

`text(Graph 2)`

`∑\ text(degrees)\ = 2 + 2 + 2 + 2 + 2 + 2 = 12`

`=> C`

NETWORKS, FUR1 2009 VCAA 8 MC

An undirected connected graph has five vertices.

Three of these vertices are of even degree and two of these vertices are of odd degree.

One extra edge is added. It joins two of the existing vertices.

In the resulting graph, it is not possible to have five vertices that are

A.   all of even degree.

B.   all of equal degree.

C.   one of even degree and four of odd degree.

D.   three of even degree and two of odd degree.

E.   four of even degree and one of odd degree. 

Show Answers Only

`E`

Show Worked Solution

`text(Consider an example of the graph)`

♦♦♦ Mean mark 25%.

`text{described (below):}`
 

matrices-fur1-2009-vcaa-8-mc-answer
 

`A\ text(is possible – join)\ V\ text(and)\ Z`

`B\ text(is possible – join)\ V\ text(and)\ Z`

`C\ text(is possible – join)\ W\ text(and)\ Y`

`D\ text(is possible – join)\ V\ text(and)\ X`

`E\ text(is NOT possible)`

`=>  E`