topic badge

4.015 Types of graphs

Worksheet
Simple networks
1

Explain what we need change to make the following network simple:

2

State whether the following networks are simple:

a
b
c
d
e
f
3

The social network Bleeter allows people to share content (in the form of "Bleets") online.

Before anyone can share anything, two people must first make a connection, so one person "follows" the other. Whenever a person creates a Bleet, it is shared with everyone who follows them. These people are called "followers".

The given network represents the connections among a group of six users of Bleeter. An arrow from one vertex to another means that the first person follows the second. So DF follows BK.

a

What kind of network, directed or undirected, represents the connections people form on Bleeter?

b

Which user has the most followers?

c

Which user follows the most people?

d

Is this an example of a simple network? Explain your answer.

4

Consider the table below:

a

For each number of vertices in the first row of the table, draw a simple network and then fill in the number of edges in the resulting network in the second row of the table:

Vertices23456
Edges
b

Determine the rule that calculates the number of edges, E, given the number of vertices, V, for a simple network.

c

Hence calculate the number of edges required for a simple network with 10 vertices.

Connected graphs
5

Consider the following graph:

a

Which vertex is isolated?

b

How many edges are there?

c

How many vertices are there?

d

Which vertex is the loop connected to?

e

Is the graph simple? Explain your answer.

f

Is the graph connected? Explain your answer.

6

Determine whether the following statements are true or false in relation to undirected connected graphs:

a

There is an isolated vertex.

b

There are no loops.

c

Each vertex is linked to another vertex only through one edge.

d

Every vertex is reachable via some path from every other vertex.

7

State whether the following graphs are connected:

a
b
c
d
e
f
g
h
i
j
k
l
m
8

Consider the given disconnected network:

a

In order to make the network connected, an edge from vertex P chould be drawn to which other vertices?

b

If edge WU is added, will there be a path from P to Q?

9

Consider the given disconnected directed network:

a

In order to make the network connected, an edge from vertex P could be drawn to which other vertex?

b

After adding this edge, is there now a path from R to P?

10

Consider the following diagram:

a

State the number of vertices.

b

State the number of edges.

c

Copy and complete the following table:

VertexABCDE
Degree
d

Is the graph connected or disconnected?

11

Consider the following diagram:

a

State the number of vertices.

b

State the number of edges.

c

Describe the graph as connected or disconnected.

d

Complete the table below:

VertexABCDEFG
Degree
Subgraphs and bipartite graphs
12

For the following pairs of graphs, determine whether Graph 2 is a subgraph of Graph 1:

a

Graph 1

Graph 2

b

Graph 1

Graph 2

c

Graph 1

Graph 2

13

Find the weight of each highlighted subgraph:

a
b
14

Consider the given graph:

a

Find the weight of the subgraph formed by the vertices P, S, and V.

b

Find the weight of the subgraph formed by deleting vertices V, W, T, and S, along with all connecting edges.

15

State whether the following graphs are bipartite graphs:

a
b
c
d
e
f
g
h
i
j
k
l
Complete graphs
16

State whether the following graphs are complete graphs:

a
b
c
d
e
f
g
h
i
j
k
l
17

Determine the number of edges in a complete graph which has:

a

3 vertices

b

4 vertices

c

5 vertices

d

n vertices

18

Determine the number of vertices in a complete graph which has 6 edges.

19

A complete bipartite graph is a special kind of bipartite graph where every vertex of the one group is connected to every vertex of the other group. State whether the following are complete bipartite graphs:

a
b
c
d
e
f
g
h
i
j
k
l
20

Determine the number of edges in a complete bipartite graph which has:

a

2 vertices in each group.

b

3 vertices in each group.

c

4 vertices in each group.

d

n vertices in each group.

21

Write down the terms that describe each of the following graphs from the list of terms below:

  • Complete

  • Connected

  • Simple

  • Directed

  • Bipartite

  • Weighted

a
b
c
Sign up to access Worksheet
Get full access to our content with a Mathspace account

Outcomes

3.3.1

demonstrate the meanings of, and use, the terms: graph, edge, vertex, loop, degree of a vertex, subgraph, simple graph, complete graph, bipartite graph, directed graph (digraph), arc, weighted graph, and network

What is Mathspace

About Mathspace