Font size
WorksheetsGraph Theory
Total questions: 40
Worksheet time: 20mins
Which set represents the vertices of the graph?
{1,2}, {2,3}. {2,4}, {4,5}, {4,6}
{1, 2, 3, 4, 5, 6,}
{1, 2, 3, 4, 5, 6, 7}
{1,2}, {2,3}. {2,4}, {4,5}, {4,6}, {6,7}
What is the degree of vertex 4?
3
4
5
7
Which two vertices are adjacent vertices?
5 is adjacent to 6
3 is adjacent to 6
4 is adjacent to 1
3 is adjacent to 2
The graph represents the following vocabulary term.
Cycle
Path
Complete Graph
Complete Bipartite Graph
The graph is an example of a
Path
Cycle
Complete Bipartite Graph
Complete Graph
Which vocabulary term describes the graph?
circuit
path
complete graph
polygon
What is the weight of the shortest path from A to F?
5
7
9
11
Which vertices are adjacent to E?
B and C
B, C, D, and A
B
A, B, C, D, F, G
Which of the following are isolated vertices?
F
G
Graphs are fun.
F and G
Which notation is correct for the complete bipartite graph?
K2,3
K3
K2
K1, 3
The degree of any vertex of graph is .... ?
The number of edges incident with vertex
Number of vertex in a graph
Number of vertices adjacent to that vertex
Number of edges in a graph
Which of the following is true?
A graph may contain no edges and many vertices
A graph may contain many edges and no vertices
A graph may contain no edges and no vertices
A graph may contain no vertices and many edges
Which of the statements below is not true
V = {P, Q, R, S, T, U}
E = {(R,S), (S,T), (T,U), (U,P), (P,Q)}
d(R) = 3
sum of degree = 18
Which of the following statements in not true?
V={ P, Q, R, S, T, U}
E= {(P,P), (P,R), (R,S), (S,T), (T,S), (R,Q), (Q,P)}
d(P) = 3
sum of degree = 14
Which of the following statements in not true?
V = { P, Q, R, S, T}
E = { (P,Q), (Q,R), (S,R), (S,T), (T,T), (P,S), (S,P)}
din (T) = 2
sum of degree = 14
The directed graph on the right shows the
roads connecting Lani’s house at A to the
school at E. Suggest the shortest route
that Lani can choose to cycle to school.
A > C > D > E
A > B > C > E
A > D > E
A > B > E
The directed weighted graph on the right shows
the prices of tickets and the travel times for some
choices of flights of a private airline. Vertex S is the
destination of the flight from vertex P. Vertex Q and
vertex R are the transit airports. The transit time at
each of the airports is 45 minutes. Which one is the most economical route?
P > Q > R > S
P > R > S
P > Q > S
P > S
The directed weighted graph on the right shows
the prices of tickets and the travel times for some
choices of flights of a private airline. Vertex S is the
destination of the flight from vertex P. Vertex Q and
vertex R are the transit airports. The transit time at
each of the airports is 45 minutes. Which route takes the shortest time?
P > Q > R > S
P > R > S
P > Q > S
P > S
The following undirected graph shows six houses in a village. A salesperson needs to visit all
the houses starting from house A and finishing at house F. Calculate the shortest distance in km.
3.05
3.08
3.30
3.68
A simple graph has no loops. What other property must a simple graph have?
It must be directed.
It must be undirected.
It must have at least one vertex.
It must have no multiple edges.
You are required to construct a graph with 20 edges and each vertex with a degree of 4. How many vertices do you need to have on the graph?
8
10
12
15
Which one is NOT a subgraph of the above graph?
Which of the following statements is/are TRUE for undirected graphs?
P: Number of odd degree vertices is even.
Q: Sum of degrees of all vertices is even.
P only
Q only
Both P and Q
Neither P nor Q
Is the given Graph is regular?
Yes
No
What will be the number of edges in a complete bipartite graph Km,n
m+n
m.n
Data Insufficient
Which of the following is a correct representation of a complete bipartite graph?
K2,2
K4
K5
C3
Determine the sum of degrees.
16
8
4
13
Graphs that have directed edges are called
multiple edges
simple graphs
digraphs
trees
Which graphs are simple? (select all that apply)
None are simple graphs
A (a) is a route through a graph along edges in which no vertex is visited more than once
Euler's Handshaking Lemma says that the sum of the degrees of the vertices is equal to 2 x the number of (a)
A path that starts and finishes at the same vertex.
cycle
trail
closed walk
loop
A walk that involves no repeat use of edges and no repeat use of vertices.
path
bridge
trail
length
If I want to travel every edge once and I don't mind repeating vertices, I need to think...
Bipartite graph
Hamiltonian path
Complete graph
Eulerian trail
An edge that starts and finishes at the same vertex.
node
loop
arc
multiple edges
Vertices are divided into two disjoint sets. Edges do NOT join vertices from the same group.
Planar graph
Bipartite graph
Complete graph
Linear graph
The number of edges a walk, trail, path or cycle uses.
Multiple edges
Length
Degree
Order
Choose all the simple graph below.
Choose all the graphs with multi edges and / loop(s).
Choose all the correct information about the simple graph given.
n(V) = 4
n(V) = 5
n(E) = 4
n(E) = n(V)
Sum of degree = 10
