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.

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?

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.

Practise

Open Math

Network concepts

Discrete Mathematics · MST-11-07

Name:

Date:

Q1Straightforward

A network has vertices

A

B

C

D

with edges

AB

BC

CD

DA

and

AC

. How many edges does the network have?

Q2Straightforward

A network has vertices

P

Q

R

S

with edges

PQ

PR

QR

QS

and

RS

. What is the degree of vertex

Q

Q3Straightforward

A network has vertices

A

B

C

D

E

with edges

AB

BC

CD

CE

and

DE

. What is the degree of vertex

C

Q4Straightforward

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

A.The number of edges connected to that vertex
B.The total number of vertices in the network
C.The weight of the shortest path from that vertex
D.The number of cycles passing through that vertex

Q5Moderate

A network has 6 vertices

A

B

C

D

E

F

with edges

AB

BC

CD

DE

. Which statement correctly describes this network?

A.Connected, because every vertex has at least one edge
B.Disconnected, because vertex $F$ has no edges
C.Connected, because the edges form a chain from $A$ to $E$
D.Disconnected, because the network has fewer edges than vertices

Q6Moderate

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?

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

Q7Moderate

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?

Q8Moderate

A network has vertices

P

Q

R

S

with edges

PQ

PR

QR

and

QS

. Is this network connected?

A.No, because vertex $S$ is only directly connected to one other vertex
B.Yes, because there is a path between every pair of vertices
C.No, because not all vertices have the same degree
D.Yes, because the network contains a cycle through $P$ , $Q$ and $R$

Q9Challenging

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.

Q10Challenging

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

Q11Challenging

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?

A.Yes, because every consecutive pair is connected by an edge
B.No, because vertex $A$ appears more than once
C.Yes, because the sequence visits four different edges
D.No, because the sequence does not return to the starting vertex

Q12Challenging

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?

A.It is a valid path because no edge is repeated
B.It is a valid walk but not a valid path because vertex $A$ is repeated
C.It is neither a walk nor a path because it uses more edges than vertices
D.It is a valid path because all four vertices are visited

Worked solutions and answers at openmath.au/year-11/standard/networks-paths-and-trees/network-concepts