SmarterEd

Aussie Maths & Science Teachers: Save your time with SmarterEd

Networks, SMB-023

A new housing estate is being developed.

There are five houses under construction in one location.

These houses are numbered as points 1 to 5 below.
 

  
The builders require the five houses to be connected by electrical cables to enable the workers to have a supply of power on each site.

  1. What is the minimum number of edges needed to connect the five houses?  (1 mark)

  2. On the diagram above, draw a connected graph with this number of edges.  (1 mark) 

Show Answers Only

i.   `text(Minimum number of edges = 4)`
 

ii.   `text(One of many possibilities:)`
 

Show Worked Solution

i.   `text(Minimum number of edges = 4)`
 

ii.   `text(One of many possibilities:)`
 

Networks, SMB-022

The following graph with five vertices is a complete graph.
 

How many edges must be removed so that the graph will have the minimum number of edges to remain connected. Explain your answer.   (3 marks)

Show Answers Only

`text{6 edges need to be removed}`

Show Worked Solution

`text(The minimum number of edges for a connected graph with)`

`text{5 vertices is 4 (see one possible example below).}`
 

 
`:.\ text(Edges to be removed)\ = 10-4= 6`

Networks, SMB-021

Consider the following graph.
 

On the diagram above, make this a connected graph, using the smallest number of edges.   (2 marks)

Show Answers Only

`text{Any addition of 3 edges that connects all vertices.}`
 

Show Worked Solution

`text{Any addition of 3 edges that connects all vertices.}`
 

Networks, SMB-019

The network below can be represented as a planar graph.
 

Redraw the graph as a planar representation of the network, labelling each vertex.   (2 marks)

Show Answers Only

Show Worked Solution

`text{Redrawing the graph in planar form (no edges crossing):}` 
 

Networks, SMB-018

The network below can be represented as a planar graph.

 

Redraw the graph as a planar representation of the network, labelling each vertex.   (2 marks)

Show Answers Only

Show Worked Solution

`text{Redrawing the graph in planar form (no edges crossing):}` 
 

Networks, SMB-020 MC

The graph above has

  1. 5 faces.
  2. 6 faces.
  3. 8 faces.
  4. 9 faces.
Show Answers Only

`=> B`

Show Worked Solution

`text(Redrawing the graph in planar form,)`

`text(the graph can be seen to have 6 faces.)`
 

`text(Alternatively, using Euler’s rule:)`

`v + f` `= e + 2`
`5 + f` `= 9 + 2`
`:. f` `= 6`

 
`=> B`

Networks, SMB-017

The network below can be represented as a planar graph.
 

Redraw the graph as a planar representation of the network, labelling each vertex.   (2 marks)

Show Answers Only

Show Worked Solution

`text{Redrawing the graph in planar form (no edges crossing):}` 
 

Networks, SMB-016

The network below can be represented as a planar graph.
 

Complete the partial graph drawn below, adding the missing edges so that it is a planar representation of the above network.   (3 marks)
  

Show Answers Only

Show Worked Solution

`text{Redrawing the graph in planar form (no edges crossing):}` 
 

Networks, SMB-015

The network below can be represented as a planar graph.
 

Draw the planar graph representation of this network, labelling each vertex.   (2 marks)

Show Answers Only

Show Worked Solution

`text{Redrawing the graph in planar form (no edges crossing):}` 
 

`text{Each vertex is the same degree as the original graph and}`

`text{has edges connecting to the same vertices.}`

Networks, SMB-014

The network below can be represented as a planar graph.
 

Draw the planar graph representation of this network and find the number of faces in the planar graph.   (3 marks)

Show Answers Only

`text{Number of faces = 6}`

Show Worked Solution

`text(Redrawing the graph in planar form:)` 

`text{Method 1}`

`text{Number of faces = 6 (by inspection)}`

 
`text(Method 2 (Euler’s formula))`

`v + f` `= e + 2`
`5 + f` `= 9 + 2`
`:. f` `= 6`

Networks, SMB-013

Consider the planar graph below.
 

 
Euler’s formula will be verified for this graph.

Find the values of `e, v` and `f` and use them to verify Euler's formula.   (3 marks)

Show Answers Only

`e=6, v=5, f=3`

Show Worked Solution

`text{Number of edges:}\ e=6`

`text{Number of vertices:}\ v=5`

`text{Number of faces:}\ f=3`

`text(Verifying Euler’s formula):\ \ v + f = e + 2`

`5+3` `= 6+2`
`8` `= 8\ \ =>\ \text{Euler holds}`

Networks, SMB-012

A connected planar graph has 4 edges and 4 faces.

  1. Calculate the number of vertices for this graph.  (2 marks)
  2. Draw the planar graph.   (2 marks)
Show Answers Only

i.    `text{2 vertices}`

ii.    
         

Show Worked Solution
i.    `v+f` `=e+2`
`:. v` `=e-f + 2`
  `= 4-4 + 2`
  `= 2`

 
ii.   
           

Networks, SMB-009 MC

A planar graph has five faces.

This graph could have

  1.  six vertices and eight edges.
  2.  eight vertices and five edges.
  3.  eight vertices and six edges.
  4.  five vertices and eight edges.
Show Answers Only

`D`

Show Worked Solution

`text(Using Euler’s formula:)`

`v + f` `= e + 2`
`v + 5` `= e + 2`
`v + 3` `= e`

 
`text{Consider each option:}`

`text{5 vertices and 8 edges → Euler holds}`

`=> D`

Networks, SMB-007 MC

A connected planar graph has 12 edges.

This graph could have

  1. 5 vertices and 6 faces.
  2. 5 vertices and 8 faces.
  3. 6 vertices and 8 faces.
  4. 6 vertices and 9 faces.
Show Answers Only

`C`

Show Worked Solution

`text(Consider option C:)`

`v + f` `= e + 2`
`6 + 8` `= 12 + 2`
`14` `= 14`

 

 
`text(i.e. Euler’s formula holds.)`

`=>  C`

Networks, SMB-006

Consider the graph below.
 

  1. Redraw this network as a planar graph.   (1 mark)

  2. Find the number of faces on the planar graph.   (2 marks)

Show Answers Only

i.   
       

 
ii.    \(\text{Number of faces = 4}\)

Show Worked Solution

i.   
       

 
ii.    \(\text{Method 1}\)

\(\text{By inspection, number of faces = 4}\)
 

\(\text{Method 2}\)

`v-e+f` `=2`  
`4-6+f` `=2`  
`f` `=4`  

Networks, SMB-005

A network is represented by the following graph.
 

  1. Draw the above network as a planar graph.   (1 mark)
  2. Find the number of faces of this planar graph.   (2 marks)
Show Answers Only

i.    
       

ii.    \(6\)

Show Worked Solution

i.    
       

 
ii.    \(\text{Method 1}\)

\(\text{By inspection (see image above):} \)

\(\text{Number of faces = 6} \)
 

\(\text{Method 2}\)

`v-e+f` `=2`  
`8-12+f` `=2`  
`f` `=6`  

Networks, STD2 N2 EQ-Bank 30

The map of Australia shows the six states, the Northern Territory and the Australian Capital Territory (ACT).
  

In the network diagram below, each of the vertices `A` to `H` represents one of the states or territories shown on the map of Australia. The edges represent a border shared between two states or between a state and a territory.
 

  1. In the network diagram, what is the order of the vertex that represents the Australian Capital Territory (ACT)?   (1 mark)

  2. In the network diagram, Queensland is represented by which letter? Explain why.   (2 marks)

Show Answers Only

a.    `1`

b.    `text{NSW is Vertex B (it is connected to the ACT – Vertex D)}`

`=> C\ text{is Victoria as it has degree 2}`

`:.\ text(Queensland is vertex)\ A\ text(as it is connected to)\ B\ text(and has degree 3.)`

Show Worked Solution

a.     `text {ACT has 1 border (with NSW)}`

`:.\ text(Degree of ACT’s vertex = 1)`
 

b.    `text{NSW is Vertex B (it is connected to the ACT – Vertex D)}`

`=> C\ text{is Victoria as it has degree 2}`

`:.\ text(Queensland is vertex)\ A\ text(as it is connected to)\ B\ text(and has degree 3.)`

Networks, STD2 N2 2015 FUR1 5 MC

The graph below represents a friendship network. The vertices represent the four people in the friendship network: Kwan (K), Louise (L), Milly (M) and Narelle (N).

An edge represents the presence of a friendship between a pair of these people. For example, the edge connecting K and L shows that Kwan and Louise are friends.

Which one of the following graphs does not contain the same information.
 
 

Show Answers Only

`D`

Show Worked Solution

`text(Option D has Kwan and Milly as friends which is not correct.)`

`=> D`

Networks, STD2 N2 2011 FUR1 1 MC

In the network shown, the number of vertices of even degree is

  1. `2`
  2. `3`
  3. `4`
  4. `5`
Show Answers Only

`B`

Show Worked Solution

`text{Vertices with even degrees: 2, 2, 6}`

`=>  B`

Networks, STD2 N2 2017 FUR1 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. 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, STD2 N2 2010 FUR1 2 MC

 vcaa-networks-fur1-2010-2 

The number of edges in the graph above is

  1. `5`
  2. `7`
  3. `8`
  4. `10`
Show Answers Only

`C`

Show Worked Solution

`text{Edges are represented by lines between vertices.}`

`=>  C`