Graph Theory

Question 1 of 73

1

What is the formal name for the points on a graph?

Select one of the following:

Vertices
Edges

Explanation

Question 2 of 73

1

What is the formal name for the lines connecting the points on a graph?

Select one of the following:

Vertices
Edges

Explanation

Question 3 of 73

1

Fill the blank space to complete the text.

V =

Explanation

Question 4 of 73

1

Fill the blank space to complete the text.

E =

Explanation

Question 5 of 73

1

Two graphs are equal if and only if they have the same vertices and the same edges.

Select one of the following:

True
False

Explanation

Question 6 of 73

1

Two graphs are equal if and only if they have some vertices and the same edges.

Select one of the following:

True
False

Explanation

Question 7 of 73

1

Fill the blank space to complete the text.

We say that two graphs G and H are if we can relabel the vertices of G to obtain H.

Explanation

Question 8 of 73

1

Fill the blank space to complete the text.

The of a graph G is the number of vertices of G

Explanation

Question 9 of 73

1

Fill the blank space to complete the text.

The order of a graph G is the number of of G

Explanation

Question 10 of 73

1

Fill the blank space to complete the text.

The of G is the number of edges of G

Explanation

Question 11 of 73

1

Fill the blank space to complete the text.

The size of G is the number of of G

Explanation

Question 12 of 73

1

We often write ❌ as shorthand for an edge {u,v}

Drag and drop to complete the text.

uv

{uv}

Explanation

Question 13 of 73

1

Fill the blank space to complete the text.

We often write uv as shorthand for an edge {}

Explanation

Question 14 of 73

1

Select from the dropdown list to complete the text.

We say that an edge e = uv is ( incident, adjacent ) to the vertices u and v.

Explanation

Question 15 of 73

1

Select from the dropdown list to complete the text.

If uv is an edge, we say that the vertices u and v are ( adjacent, incident )

Explanation

Question 16 of 73

1

Fill the blank space to complete the text.

u is a of v and that v is a neighbour of u.

Explanation

Question 17 of 73

1

Fill the blank space to complete the text.

For any vertex v of a graph G, the N(v) of v is the set of neighbours of v

Explanation

Question 18 of 73

1

For any vertex v of a graph G, the ............. of v is the set of neighbours of v

Select one or more of the following:

neighbourhood N(v)
neighbourhood N(u)
compliment N(v)
neighbourhood G(v)
neighbourhood d(v)
neighbourhood N(G)

Explanation

Question 19 of 73

1

Fill the blank space to complete the text.

We say that v is isolated if it has no .

Explanation

Question 20 of 73

1

Select from the dropdown list to complete the text.

We say that v is ( isolated, complementary, distinct, incident, adjacent ) if it has no neighbours.

Explanation

Question 21 of 73

1

Fill the blank space to complete the text.

The neighbourhood of a is N(a) =

Explanation

Question 22 of 73

1

Fill the blank space to complete the text.

The neighbourhood of d is N (d) =

Explanation

Question 23 of 73

1

Fill the blank space to complete the text.

The neighbourhood of e is N(e) =

Explanation

Question 24 of 73

1

Vertex e is ........ vertex

Select one of the following:

an isolated
an adjacent
a

Explanation

Question 25 of 73

1

Fill the blank space to complete the text.

Vertex e is an vertex

Explanation

Question 26 of 73

1

The degree of a vertex v in a graph G is d(v) = |N(v)|, that is,

Select one or more of the following:

The number of neighbours of v
The number of edges of v
The number of vertices of v
The number of v

Explanation

Question 27 of 73

1

d(v) =

Select one of the following:

|N(v)|
|G(v)|
0

Explanation

Question 28 of 73

1

Fill the blank spaces to complete the text.

The vertex degrees are
d(a) = ,
d(b) = ,
d(c) = ,
d(d) =
d(e) = .

Explanation

Question 29 of 73

1

If G is a graph with n vertices, then the degree of each vertex of G is an integer between 0 and n − 1.

Select one of the following:

True
False

Explanation

Question 30 of 73

1

Fill the blank spaces to complete the text.

If G is a graph with n vertices, then the degree of each vertex of G is an integer between and .

Explanation

Question 31 of 73

1

Fill the blank space to complete the text.

If G is a graph with n vertices, then the of each vertex of G is an integer between 0 and n − 1.

Explanation

Question 32 of 73

1

The sum of all vertex degrees is twice the number of edges

Select one of the following:

True
False

Explanation

Question 33 of 73

1

Fill the blank space to complete the text.

the sum of all vertex degrees is the number of edges

Explanation

Question 34 of 73

1

Fill the blank space to complete the text.

The sum of all vertex degrees is twice the number of

Explanation

Question 35 of 73

1

Fill the blank space to complete the text.

The sum of all vertex is twice the number of edges

Explanation

Question 36 of 73

1

In any graph there are an even number of vertices with odd degree.

Select one of the following:

True
False

Explanation

Question 37 of 73

1

In any graph there are an even number of edges with odd degree.

Select one of the following:

True
False

Explanation

Question 38 of 73

1

Fill the blank space to complete the text.

Any graph on at least two vertices has two vertices of the same .

Explanation

Question 39 of 73

1

Fill the blank space to complete the text.

The of a graph G is the sequence of all degrees of vertices in G

Explanation

Question 40 of 73

1

Fill the blank spaces to complete the text.

The of a graph G, denoted δ(G), is the degree of a vertex of G.

Explanation

Question 41 of 73

1

Fill the blank spaces to complete the text.

The of a graph G, denoted ∆(G), is the of a vertex of G.

Explanation

Question 42 of 73

1

Fill the blank space to complete the text.

A graph G is if every vertex of G has the same degree

Explanation

Question 43 of 73

1

We say that G is k-regular to mean that every vertex has degree k.

Select one of the following:

True
False

Explanation

Question 44 of 73

1

Fill the blank space to complete the text.

We say that G is -regular to mean that every vertex has degree k.

Explanation

Question 45 of 73

1

Fill the blank space to complete the text.

We say that G is to mean that every vertex has degree k.

Explanation

Question 46 of 73

1

Fill the blank space to complete the text.

A graph H is a of a graph G if we can obtain H by deleting vertices and edges of G.

Explanation

Question 47 of 73

1

Fill the blank space to complete the text.

A graph H is a subgraph of a graph G if we can obtain H by vertices and edges of G

Explanation

Question 48 of 73

1

Select from the dropdown list to complete the text.

H is a ( spanning, "blank", copy ) subgraph of G if additionally V (H) = V (G), that is, if only edges were deleted.

Explanation

Question 49 of 73

1

Select from the dropdown list to complete the text.

H is a ( subgraph, graph, spanning subgraph, copy ) of a graph G if we can obtain H by deleting vertices and edges of G.

Explanation

Question 50 of 73

1

Let G be a graph with δ(G) ≥ 2. Then G contains a cycle.

Select one of the following:

True
False

Explanation

Question 51 of 73

1

Let G be a graph with δ(G) ≥ 0. Then G contains a cycle.

Select one of the following:

True
False

Explanation

Question 52 of 73

1

Let G be a graph with N(G) ≥ 2. Then G contains a cycle.

Select one of the following:

True
False

Explanation

Question 53 of 73

1

Any graph with n vertices and at least n edges contains a cycle

Select one of the following:

True
False

Explanation

Question 54 of 73

1

Any graph with n vertices and at least n-1 edges contains a cycle

Select one of the following:

True
False

Explanation

Question 55 of 73

1

Any graph with n+1 vertices and at least n edges contains a cycle

Select one of the following:

True
False

Explanation

Question 56 of 73

1

Select from the dropdown list to complete the text.

The length of W is the number of ( edges, vertices ) traversed

Explanation

Question 57 of 73

1

A walk is closed if the first and last vertices of the walk are the same, that is, if you finish at the same vertex at which you started.

Select one of the following:

True
False

Explanation

Question 58 of 73

1

A walk is open if the first and last vertices of the walk are the same, that is, if you finish at the same vertex at which you started.

Select one of the following:

True
False

Explanation

Question 59 of 73

1

A walk is a path if and only if it has no repeated vertices

Select one of the following:

True
False

Explanation

Question 60 of 73

1

walk is a path if and only if it has repeated vertices

Select one of the following:

True
False

Explanation

Question 61 of 73

1

A closed walk is a cycle if and only if the only repeated vertex is the first and last vertex

Select one of the following:

True
False

Explanation

Question 62 of 73

1

A closed walk is a cycle if and only if there is a repeated vertex at the first and last vertex

Select one of the following:

True
False

Explanation

Question 63 of 73

1

Fill the blank space to complete the text.

A graph G is if for any two vertices u and v of G there is a walk in G from u to v.

Explanation

Question 64 of 73

1

A ❌ of G is a maximal connected subgraph of G

Drag and drop to complete the text.

connected component

component

subgraph

tree

cycle

Explanation

Question 65 of 73

1

A tree is a ❌ ❌ graph.

Drag and drop to complete the text.

connected

component

walk

path

unconnected

join

acyclic

walks

paths

cyclic

Explanation

Question 66 of 73

1

A ❌ of a tree is a vertex v with d(v) = ❌.

Drag and drop to complete the text.

leaf

edge

vertex

1

2

0

5

Explanation

Question 67 of 73

1

Any tree on n ≥ 2 vertices has a leaf.

Select one of the following:

True
False

Explanation

Question 68 of 73

1

Any tree on n ≥ 0 vertices has a leaf.

Select one of the following:

True
False

Explanation

Question 69 of 73

1

Any connected graph contains a spanning tree

Select one of the following:

True
False

Explanation

Question 70 of 73

1

Any connected graph on n vertices with precisely n − 1 edges is a tree

Select one of the following:

True
False

Explanation

Question 71 of 73

1

Any connected graph on n vertices with precisely n edges is a tree

Select one of the following:

True
False

Explanation

Question 72 of 73

1

Any acyclic graph on n vertices with precisely n − 1 edges is a tree.

Select one of the following:

True
False

Explanation

Question 73 of 73

1

Any acyclic graph on n vertices with precisely n edges is a tree.

Select one of the following:

True
False

	Created by Will Rickard over 8 years ago

Bachelors Degree Mathematics Quiz on Graph Theory, created by Will Rickard on 01/04/2016.

Graph Theory

Question 1 of 73

What is the formal name for the points on a graph?

Select one of the following:

Explanation

Question 2 of 73

What is the formal name for the lines connecting the points on a graph?

Select one of the following:

Explanation

Question 3 of 73

Fill the blank space to complete the text.

V =

Explanation

Question 4 of 73

Fill the blank space to complete the text.

E =

Explanation

Question 5 of 73

Two graphs are equal if and only if they have the same vertices and the same edges.

Select one of the following:

Explanation

Question 6 of 73

Two graphs are equal if and only if they have some vertices and the same edges.

Select one of the following:

Explanation

Question 7 of 73

Fill the blank space to complete the text.

We say that two graphs G and H are if we can relabel the vertices of G to obtain H.

Explanation

Question 8 of 73

Fill the blank space to complete the text.

The of a graph G is the number of vertices of G

Explanation

Question 9 of 73

Fill the blank space to complete the text.

The order of a graph G is the number of of G

Explanation

Question 10 of 73

Fill the blank space to complete the text.

The of G is the number of edges of G

Explanation

Question 11 of 73

Fill the blank space to complete the text.

The size of G is the number of of G

Explanation

Question 12 of 73

We often write ❌ as shorthand for an edge {u,v}

Drag and drop to complete the text.

Explanation

Question 13 of 73

Fill the blank space to complete the text.

We often write uv as shorthand for an edge {}

Explanation

Question 14 of 73

Select from the dropdown list to complete the text.

We say that an edge e = uv is incident adjacent( incident, adjacent ) to the vertices u and v.

Explanation

Question 15 of 73

Select from the dropdown list to complete the text.

If uv is an edge, we say that the vertices u and v are adjacent incident( adjacent, incident )

Explanation

Question 16 of 73

Fill the blank space to complete the text.

u is a of v and that v is a neighbour of u.

Explanation

Question 17 of 73

Fill the blank space to complete the text.

For any vertex v of a graph G, the N(v) of v is the set of neighbours of v

Explanation

Question 18 of 73

For any vertex v of a graph G, the ............. of v is the set of neighbours of v

Select one or more of the following:

Explanation

Question 19 of 73

Fill the blank space to complete the text.

We say that v is isolated if it has no .

Explanation

Question 20 of 73

Select from the dropdown list to complete the text.

We say that an edge e = uv is ( incident, adjacent ) to the vertices u and v.

If uv is an edge, we say that the vertices u and v are ( adjacent, incident )

We say that v is ( isolated, complementary, distinct, incident, adjacent ) if it has no neighbours.

The vertex degrees are
d(a) = ,
d(b) = ,
d(c) = ,
d(d) =
d(e) = .