Open Math›Year 11›Mathematics Standard›Networks, paths and trees›Network concepts

Network concepts

Identify vertices, edges and vertex degrees in a network; classify networks as connected or disconnected; apply the handshaking lemma and distinguish between paths and walks.

Worked examples

Finding the degree of each vertex in a network

Straightforward

Problem

A network has vertices

A

B

C

D

with edges

AB

BC

CD

DA

and

BD

. State the number of edges in the network and find the degree of each vertex.

Count the edges by listing them.

Edges:

AB

BC

CD

DA

BD

— there are

5

edges.

Find the degree of

A

by listing every edge that includes

A

AB

DA

— degree of

A = 2

Find the degree of

B

by listing every edge that includes

B

AB

BC

BD

— degree of

B = 3

Find the degree of

C

by listing every edge that includes

C

BC

CD

— degree of

C = 2

Find the degree of

D

by listing every edge that includes

D

CD

DA

BD

— degree of

D = 3

Answer

The network has

5

edges.

\deg(A) = 2

\deg(B) = 3

\deg(C) = 2

\deg(D) = 3

Classifying a network as connected or disconnected

Moderate

Problem

A network has

5

vertices

P

Q

R

S

T

with edges

PQ

(weight 6),

PR

(weight 4),

QR

(weight 5) and

QT

(weight 8). (a) Is this network connected? (b) What is the total weight of all edges?

List all vertices and check which ones appear in at least one edge.

Vertices in edges:

P

(in

PQ

PR

Q

(in

PQ

QR

QT

R

(in

PR

QR

T

(in

QT

). Vertex

S

does not appear in any edge.

Since

S

has no edges, determine whether the network is connected.

Vertex

S

is isolated — there is no path from

S

to any other vertex. The network is disconnected.

Calculate the total weight of all edges.

\text{Total weight} = 6 + 4 + 5 + 8 = 23

Answer

(a) The network is disconnected — vertex

S

is isolated. (b) The total weight is

23

Applying the handshaking lemma and identifying paths and walks

Challenging

Problem

A network has

5

vertices. Four of the vertices have degrees

4

3

2

and

3

. The network has

7

edges. (a) Use the handshaking lemma to find the degree of the fifth vertex. (b) A network with vertices

A

B

C

D

and edges

AB

BC

CD

DA

AC

has the proposed vertex sequence

B, C, A, B, D

. Explain whether this sequence is a valid path or walk.

Apply the handshaking lemma to find the sum of all vertex degrees.

\text{Sum of all degrees} = 2 \times \text{number of edges} = 2 \times 7 = 14

Find the degree of the fifth vertex by subtracting the four known degrees.

\text{Degree of fifth vertex} = 14 - (4 + 3 + 2 + 3) = 14 - 12 = 2

Check whether every consecutive pair in the sequence

B, C, A, B, D

is connected by an edge.

BC

✓,

CA

(same as

AC

) ✓,

AB

✓,

BD

— edge

BD

does not exist in the network. The sequence is neither a valid walk nor a valid path.

If the sequence were a valid walk, determine whether it would also be a valid path.

Vertex

B

appears at positions 1 and 4. Even if all edges existed, the repeated vertex

B

would mean it could not be a path. A path requires every vertex to appear at most once.

Answer

(a) The degree of the fifth vertex is

2

. (b) The sequence

B, C, A, B, D

is not a valid walk (edge

BD

does not exist) and therefore also not a valid path. Even if the edge existed, the repeated vertex

B

would disqualify it as a path.

Practise

Q1·Straightforward

A network has vertices

A

B

C

D

with edges

AB

BC

CD

DA

and

AC

. How many edges does the network have?

Explanation

The edges are

AB

BC

CD

DA

and

AC

. Counting each edge once gives

5

edges.

Q2·Straightforward

A network has vertices

P

Q

R

S

with edges

PQ

PR

QR

QS

and

RS

. What is the degree of vertex

Q

Explanation

Vertex

Q

appears in edges

PQ

QR

and

QS

. The degree of

Q

3

Q3·Straightforward

A network has vertices

A

B

C

D

E

with edges

AB

BC

CD

CE

and

DE

. What is the degree of vertex

C

Explanation

Vertex

C

appears in edges

BC

CD

and

CE

. The degree of

C

3

Q4·Straightforward

In a network diagram, what does the degree of a vertex represent?

The number of edges connected to that vertexThe total number of vertices in the networkThe weight of the shortest path from that vertexThe number of cycles passing through that vertex

Explanation

The degree of a vertex is the number of edges that are connected to (or incident at) that vertex.

Q5·Moderate

A network has 6 vertices

A

B

C

D

E

F

with edges

AB

BC

CD

DE

. Which statement correctly describes this network?

Connected, because every vertex has at least one edgeDisconnected, because vertex $F$ has no edgesConnected, because the edges form a chain from $A$ to $E$Disconnected, because the network has fewer edges than vertices

Explanation

Vertices

A

B

C

D

E

are all linked by the chain

A

–

B

–

C

–

D

–

E

, but vertex

F

has no edges so it cannot be reached from any other vertex. The network is disconnected.

Q6·Moderate

A network has vertices

A

B

C

D

E

with edges

AB

(weight 5),

BC

(weight 3),

CD

(weight 7) and

BE

(weight 2). Is this network connected?

Yes, because there is a path from $A$ to every other vertexNo, because vertex $D$ has degree 1No, because vertex $E$ is only directly connected to $B$Yes, because every vertex has degree at least 1

Explanation

From

A

A

–

B

reaches

B

;

A

–

B

–

C

reaches

C

;

A

–

B

–

C

–

D

reaches

D

;

A

–

B

–

E

reaches

E

. Every vertex is reachable from

A

, so the network is connected.

Q7·Moderate

A connected network has vertices

W

X

Y

Z

with edges

WX

(weight 8),

WY

(weight 5),

XY

(weight 3),

XZ

(weight 6) and

YZ

(weight 4). What is the total weight of all edges?

Explanation

\text{Total weight} = 8 + 5 + 3 + 6 + 4 = 26

Q8·Moderate

A network has vertices

P

Q

R

S

with edges

PQ

PR

QR

and

QS

. Is this network connected?

No, because vertex $S$ is only directly connected to one other vertexYes, because there is a path between every pair of verticesNo, because not all vertices have the same degreeYes, because the network contains a cycle through $P$, $Q$ and $R$

Explanation

From

S

S

–

Q

reaches

Q

;

S

–

Q

–

P

reaches

P

;

S

–

Q

–

R

reaches

R

. Every pair of vertices has a path between them, so the network is connected. A vertex with degree 1 can still belong to a connected network.

Q9·Challenging

A network has

5

vertices. The degrees of four of the vertices are

3

2

4

and

2

. The network has

7

edges. Using the handshaking lemma, find the degree of the fifth vertex.

Explanation

By the handshaking lemma:

\text{Sum of all degrees} = 2 \times 7 = 14

The sum of the four known degrees is

3 + 2 + 4 + 2 = 11

\text{Degree of fifth vertex} = 14 - 11 = 3

Q10·Challenging

A network has

5

vertices

A

B

C

D

E

and

8

edges. The degrees of

A

B

C

and

D

are

4

3

2

and

4

respectively. Using the handshaking lemma, find the degree of vertex

E

Explanation

By the handshaking lemma:

\text{Sum of all degrees} = 2 \times 8 = 16

The sum of the four known degrees is

4 + 3 + 2 + 4 = 13

\text{Degree of } E = 16 - 13 = 3

Q11·Challenging

A network has vertices

A

B

C

D

with edges

AB

BC

CD

DA

and

AC

. Consider the vertex sequence

A, B, C, A, D

. Is this a valid path?

Yes, because every consecutive pair is connected by an edgeNo, because vertex $A$ appears more than onceYes, because the sequence visits four different edgesNo, because the sequence does not return to the starting vertex

Explanation

Checking the edges:

AB

✓,

BC

✓,

CA

(same as

AC

) ✓,

AD

(same as

DA

) ✓ — so every consecutive pair is connected. However, vertex

A

appears at positions 1 and 4, so the sequence is not a valid path. It is, however, a valid walk.

Q12·Challenging

A network has vertices

A

B

C

D

with edges

AB

BC

CD

and

DA

. Consider the vertex sequence

A, B, C, D, A

. Which statement is correct?

It is a valid path because no edge is repeatedIt is a valid walk but not a valid path because vertex $A$ is repeatedIt is neither a walk nor a path because it uses more edges than verticesIt is a valid path because all four vertices are visited

Explanation

Checking the edges:

AB

✓,

BC

✓,

CD

✓,

DA

✓ — all exist, so the sequence is a valid walk. However, vertex

A

appears at both the start (position 1) and the end (position 5), so the sequence is not a valid path. It is a valid closed walk (a cycle).