Networks, SMB-006

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.

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

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

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

For an Eulerian trail to exist, what is the minimum number of extra edges that the graph would require, giving reasons. (2 marks)

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

Show Answers Only

Show Worked Solution

i. `text(Vertex)\ F`

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

`text(6 vertices are odd)`

`text{Konigsberg Bridge concept: Eulerian trail can exist if 2 vertices (only) are odd}`

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

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