smc-626-40-Euler’s Formula

Networks, GEN1 2024 NHT 37 MC

Euler's formula can be applied to which of the following graphs?

Graph 4 only
Graphs 1 and 2 only
Graphs 1, 2, 3 and 4
Graphs 3 and 4 only
Graphs 2, 3 and 4 only

Show Answers Only

$E$

Show Worked Solution

$\text{Euler’s formula applies to planar graphs.}$

$\text{Graph 1 has a complete pentagon \(\Rightarrow$ cannot be drawn as a planar graph.}\)

$\text{Graph 4 is already planar.}$

$\text{Graph 2 and 3 can both be drawn as a planar graphs.}$

$\Rightarrow E$

Networks, GEN1 2024 VCAA 35 MC

Consider the following graph.

The number of faces is

Show Answers Only

$B$

Show Worked Solution

$\text{Method 1: Make the diagram planar}$

♦ Mean mark 52%.

$\text{Method 2: Euler’s Rule}$

$\text{Vertices}\ =7,\ \text{Edges}\ =11$

$v+f$	$=e+2$
$7+f$	$=11+2$
$f$	$=6$

$\Rightarrow B$

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.

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

--- 1 WORK AREA LINES (style=lined) ---
Euler's formula, $v+f=e+2$, holds for this graph.
i. Complete the formula by writing the appropriate numbers in the boxes provided below. (1 mark)

--- 0 WORK AREA LINES (style=lined) ---
ii. Complete the sentence by writing the appropriate word in the space provided below. (1 mark)

--- 0 WORK AREA LINES (style=lined) ---

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

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)

--- 0 WORK AREA LINES (style=lined) ---

\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}$

\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}$

\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, FUR1 2020 VCAA 1 MC

A connected planar graph has seven vertices and nine edges.

The number of faces that this graph will have is

Show Answers Only

`D`

Show Worked Solution

`v + f `	`= e + 2`
`7 + f `	`= 11`
`f`	`= 4`

`=> D`

NETWORKS, FUR1-NHT 2019 VCAA 2 MC

Consider the graph below.

Euler’s formula will be verified for this graph.

What values of `e, v` and `f` will be used in this verification?

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

Show Answers Only

`D`

Show Worked Solution

`text(Euler):\ \ v + f = e + 2`

`v`	`= 5`
`e`	`= 6`
`:. f`	`= 3`

`=> D`

NETWORKS, FUR1 2018 VCAA 3 MC

A planar graph has five faces.

This graph could have

eight vertices and eight edges.
six vertices and eight edges.
eight vertices and five edges.
eight vertices and six edges.
five vertices and eight edges.

Show Answers Only

`E`

Show Worked Solution

`text(Using Euler’s formula:)`

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

`:. 5\ text(vertices and 8 edges ⇒ Euler holds)`

`=> E`

NETWORKS, FUR2 2017 VCAA 1

Bus routes connect six towns.

The towns are Northend (`N`), Opera (`O`), Palmer (`P`), Quigley (`Q`), Rosebush (`R`) and Seatown (`S`).

The graph below gives the cost, in dollars, of bus travel along these routes.

Bai lives in Northend (`N`) and he will travel by bus to take a holiday in Seatown (`S`).

Bai considers travelling by bus along the route Northend (`N`) – Opera (`O`) – Seatown (`S`).

How much would Bai have to pay? (1 mark)

--- 2 WORK AREA LINES (style=lined) ---
If Bai takes the cheapest route from Northend (`N`) to Seatown (`S`), which other town(s) will he pass through? (1 mark)

--- 2 WORK AREA LINES (style=lined) ---
Euler’s formula, `v + f = e + 2`, holds for this graph.
Complete the formula by writing the appropriate numbers in the boxes provided below. (1 mark)

--- 0 WORK AREA LINES (style=lined) ---

Show Answers Only

a. `$120`

b. `text(Quigley and Rosebush.)`

Show Worked Solution

a.	`text(C)text(ost)`	`= 15 + 105`
		`= $120`

b. `text(Cheapest route is)\ N – Q – R – S`

`:.\ text(Other towns are Quigley and Rosebush.)`

NETWORKS, FUR1 2008 VCAA 7 MC

The graph above has

4 faces.
5 faces.
6 faces.
8 faces.
9 faces.

Show Answers Only

`=> C`

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`

`=> C`

NETWORKS, FUR1 2008 VCAA 5 MC

A connected planar graph has five vertices, `A`, `B`, `C`, `D` and `E`.

The degree of each vertex is given in the following table.

Which one of the following statements regarding this planar graph is true?

A. The sum of degrees of the vertices equals 15.

B. It contains more than one Eulerian path.

C. It contains an Eulerian circuit.

D. Euler’s formula `v + f = e + 2` could not be used.

E. The addition of one further edge could create an Eulerian path.

Show Answers Only

`=> E`

Show Worked Solution

`text(Consider)\ E,`

♦ Mean mark 41%.

`text(If one edge added, the planar graph would)`

`text(have exactly 2 vertices that are odd, and an)`

`text(Eulerian path could exist.)`

`=> E`

NETWORKS, FUR1 2007 VCAA 2 MC

A connected planar graph has 12 edges.

This graph could have

5 vertices and 6 faces.
5 vertices and 8 faces.
6 vertices and 8 faces.
6 vertices and 9 faces.
7 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, FUR1 2009 VCAA 4 MC

A connected planar graph has 10 edges and 10 faces.

The number of vertices for this graph is

`2`
`5`
`8`
`12`
`20`

Show Answers Only

`A`

Show Worked Solution

`v+f`	`=e+2`
`:. v`	`= e-f + 2`
	`= 10-10 + 2`
	`= 2`

`=> A`

NETWORKS, FUR1 2015 VCAA 2 MC

A planar graph has five vertices and six faces.

The number of edges is

`3`
`6`
`9`
`11`
`13`

Show Answers Only

`C`

Show Worked Solution

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

`=> C`

\(v+f\)	\(=e+2\)
\(7+f\)	\(=11+2\)
\(f\)	\(=6\)