smc-626-30-Planar/Isomorphic

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, GEN1 2022 VCAA 4 MC

Consider the graph below.

The number of edges that need to be removed for this graph to be planar is

Show Answers Only

\(A\)

Show Worked Solution

\(\text{The graph can be drawn as follows with no crossing edges.}\)

\(\Rightarrow A\)

♦♦♦ Mean mark 21%.

NETWORKS, FUR1 2021 VCAA 3 MC

Consider the graph below.

The number of faces is

Show Answers Only

`C`

Show Worked Solution

`text{Redraw the graph so it is planar.}`

♦ Mean mark 34%.

`=> C`

NETWORKS, FUR1-NHT 2019 VCAA 6 MC

Four graphs are shown below.

How many of these graphs are planar?

Show Answers Only

`D`

Show Worked Solution

`text(Graph 1)\ =>\ text(planar)`

`text(Graph 2)\ =>\ text(planar)`

`text(Graph 3)\ =>\ text(not planar)`

`text(Graph 4)\ =>\ text(planar)`

`=> D`

NETWORKS, FUR1 2019 VCAA 4 MC

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

Which one of the following statements is not true?

Graph 1 and Graph 2 are isomorphic.
Graph 1 has five edges and Graph 2 has six edges.
Both Graph 1 and Graph 2 are connected graphs.
Both Graph 1 and Graph 2 have three faces each.
Neither Graph 1 nor Graph 2 are complete graphs.

Show Answers Only

`A`

Show Worked Solution

`text(Graph 1 → 5 edges)`

`text(Graph 2 → 6 edges)`

`:.\ text(Cannot be isomorphic.)`

`=> A`

NETWORKS, FUR1 2018 VCAA 6 MC

Which one of the following graphs is not a planar graph?

A.		B.
C.		D.
E.

Show Answers Only

`D`

Show Worked Solution

`text(Method 1)`

`text(Draw each graph with non-intersecting edges.)`

`text(This is possible for all options except)\ D.`

`text(Method 2)`

`text(Option 2 is a complete graph with five vertices.)`

`text(Any complete graph with 5 or more vertices is)`

`text(non-planar.)`

`=> D`

NETWORKS, FUR1 2016 VCAA 5 MC

Consider the planar graph below.

Which one of the following graphs can be redrawn as the planar graph above?

Show Answers Only

`A`

Show Worked Solution

`text(The degree of the 5 nodes are:)`

`4,3,3,3,3`

`text(Only option)\ A\ text(can satisfy.)`

`=> A`

NETWORKS, FUR1 2006 VCAA 8 MC

Euler’s formula, relating vertices, faces and edges, does not apply to which one of the following graphs?

Show Answers Only

`D`

Show Worked Solution

`text(Euler’s formula only applies to)`

♦♦ Mean mark 28%.
MARKER’S COMMENT: Over a third of students incorrectly chose option `A`, unaware that any graph with 4 or less vertices must be planar.

`text(planar graphs.)`

`text(Consider option)\ D,`

`text(Only option)\ D\ text(cannot be redrawn)`

`text(as a planar graph.)`

`rArr D`

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 2011 VCAA 5 MC

A network is represented by the following graph.

Which of the following graphs could not be used to represent the same network?

Show Answers Only

`E`

Show Worked Solution

`E\ text(has 2 vertices with degree 2, whereas all the)`

`text(vertices of the given network are degree 3.)`

`=> E`

NETWORKS, FUR1 2014 VCAA 6-7 MC

Consider the following four graphs.

Part 1

How many of these four graphs have an Eulerian circuit?

A. `0`

B. `1`

C. `2`

D. `3`

E. `4`

Part 2

How many of these four graphs are planar?

A. `0`

B. `1`

C. `2`

D. `3`

E. `4`

Show Answers Only

`text(Part 1:)\ B`

`text(Part 2:)\ E`

Show Worked Solution

`text(Part 1)`

`text(An Euler circuit cannot exist if any vertices)`

`text(have an odd degree.)`

`=> B`

♦♦♦ Mean mark part 2: 7%!
MARKER’S COMMENT: A majority of students chose option A, not understanding that a graph with intersecting edges can still be planar.

`text(Part 2)`

`=> E`

NETWORKS, FUR1 2015 VCAA 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

`=> D`