# Graph Theory

Quiz by Will Rickard, updated more than 1 year ago
 Created by Will Rickard about 4 years ago
118
2

### Description

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

## Resource summary

### Question 1

Question
What is the formal name for the points on a graph?
• Vertices
• Edges

### Question 2

Question
What is the formal name for the lines connecting the points on a graph?
• Vertices
• Edges

### Question 3

Question
V = [blank_start]{a,b,c,d,e}[blank_end]
• {a,b,c,d,e}

### Question 4

Question
E = [blank_start]{{a, b}, {b, c}, {a, c}, {c, d}}[blank_end]
• {{a, b}, {b, c}, {a, c}, {c, d}}

### Question 5

Question
Two graphs are equal if and only if they have the same vertices and the same edges.
• True
• False

### Question 6

Question
Two graphs are equal if and only if they have some vertices and the same edges.
• True
• False

### Question 7

Question
We say that two graphs G and H are [blank_start]isomorphic[blank_end] if we can relabel the vertices of G to obtain H.
• isomorphic

### Question 8

Question
The [blank_start]order[blank_end] of a graph G is the number of vertices of G
• order

### Question 9

Question
The order of a graph G is the number of [blank_start]vertices[blank_end] of G
• vertices

### Question 10

Question
The [blank_start]size[blank_end] of G is the number of edges of G
• size

### Question 11

Question
The size of G is the number of [blank_start]edges[blank_end] of G
• edges

### Question 12

Question
We often write [blank_start]uv[blank_end] as shorthand for an edge {u,v}
• uv
• {uv}

### Question 13

Question
We often write uv as shorthand for an edge {[blank_start]u, v[blank_end]}
• u,v

### Question 14

Question
We say that an edge e = uv is [blank_start]incident[blank_end] to the vertices u and v.
• incident

### Question 15

Question
If uv is an edge, we say that the vertices u and v are [blank_start]adjacent[blank_end]
• incident

### Question 16

Question
u is a [blank_start]neighbour[blank_end] of v and that v is a neighbour of u.
• neighbour

### Question 17

Question
For any vertex v of a graph G, the [blank_start]neighbourhood[blank_end] N(v) of v is the set of neighbours of v
• neighbourhood

### Question 18

Question
For any vertex v of a graph G, the ............. of v is the set of neighbours of v
• neighbourhood N(v)
• neighbourhood N(u)
• compliment N(v)
• neighbourhood G(v)
• neighbourhood d(v)
• neighbourhood N(G)

### Question 19

Question
We say that v is isolated if it has no [blank_start]neighbours[blank_end].
• neighbours

### Question 20

Question
We say that v is [blank_start]isolated[blank_end] if it has no neighbours.
• isolated
• complementary
• distinct
• incident

### Question 21

Question
The neighbourhood of a is N(a) = [blank_start]{b, c}[blank_end]
• {b, c}

### Question 22

Question
The neighbourhood of d is N (d) = [blank_start]{c}[blank_end]
• {c}

### Question 23

Question
The neighbourhood of e is N(e) = [blank_start]empty[blank_end]
• empty

### Question 24

Question
Vertex e is ........ vertex
• an isolated
• a

### Question 25

Question
Vertex e is an [blank_start]isolated[blank_end] vertex
• isolated

### Question 26

Question
The degree of a vertex v in a graph G is d(v) = |N(v)|, that is,
• The number of neighbours of v
• The number of edges of v
• The number of vertices of v
• The number of v

Question
d(v) =
• |N(v)|
• |G(v)|
• 0

### Question 28

Question
The vertex degrees are d(a) = [blank_start]2[blank_end], d(b) = [blank_start]2[blank_end], d(c) = [blank_start]3[blank_end], d(d) = [blank_start]1[blank_end] d(e) = [blank_start]0[blank_end].
• 2
• 2
• 3
• 1
• 0

### Question 29

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

### Question 30

Question
If G is a graph with n vertices, then the degree of each vertex of G is an integer between [blank_start]0[blank_end] and [blank_start]n − 1[blank_end].
• 0
• n − 1

### Question 31

Question
If G is a graph with n vertices, then the [blank_start]degree[blank_end] of each vertex of G is an integer between 0 and n − 1.
• degree

### Question 32

Question
The sum of all vertex degrees is twice the number of edges
• True
• False

### Question 33

Question
the sum of all vertex degrees is [blank_start]twice[blank_end] the number of edges
• twice

### Question 34

Question
The sum of all vertex degrees is twice the number of [blank_start]edges[blank_end]
• edges

### Question 35

Question
The sum of all vertex [blank_start]degrees[blank_end] is twice the number of edges
• degrees

### Question 36

Question
In any graph there are an even number of vertices with odd degree.
• True
• False

### Question 37

Question
In any graph there are an even number of edges with odd degree.
• True
• False

### Question 38

Question
Any graph on at least two vertices has two vertices of the same [blank_start]degree[blank_end].
• degree

### Question 39

Question
The [blank_start]degree sequence[blank_end] of a graph G is the sequence of all degrees of vertices in G
• degree sequence

### Question 40

Question
The [blank_start]minimum degree[blank_end] of a graph G, denoted δ(G), is the [blank_start]smallest[blank_end] degree of a vertex of G.
• minimum degree
• smallest

### Question 41

Question
The [blank_start]maximum degree[blank_end] of a graph G, denoted ∆(G), is the [blank_start]largest degree[blank_end] of a vertex of G.
• maximum degree
• largest degree

### Question 42

Question
A graph G is [blank_start]regular[blank_end] if every vertex of G has the same degree
• regular

### Question 43

Question
We say that G is k-regular to mean that every vertex has degree k.
• True
• False

### Question 44

Question
We say that G is [blank_start]k[blank_end]-regular to mean that every vertex has degree k.
• k

### Question 45

Question
We say that G is [blank_start]k-regular[blank_end] to mean that every vertex has degree k.
• k-regular

### Question 46

Question
A graph H is a [blank_start]subgraph[blank_end] of a graph G if we can obtain H by deleting vertices and edges of G.
• subgraph

### Question 47

Question
A graph H is a subgraph of a graph G if we can obtain H by [blank_start]deleting[blank_end] vertices and edges of G
• deleting

### Question 48

Question
H is a [blank_start]spanning[blank_end] subgraph of G if additionally V (H) = V (G), that is, if only edges were deleted.
• spanning
• "blank"
• copy

### Question 49

Question
H is a [blank_start]subgraph[blank_end] of a graph G if we can obtain H by deleting vertices and edges of G.
• subgraph
• graph
• spanning subgraph
• copy

### Question 50

Question
Let G be a graph with δ(G) ≥ 2. Then G contains a cycle.
• True
• False

### Question 51

Question
Let G be a graph with δ(G) ≥ 0. Then G contains a cycle.
• True
• False

### Question 52

Question
Let G be a graph with N(G) ≥ 2. Then G contains a cycle.
• True
• False

### Question 53

Question
Any graph with n vertices and at least n edges contains a cycle
• True
• False

### Question 54

Question
Any graph with n vertices and at least n-1 edges contains a cycle
• True
• False

### Question 55

Question
Any graph with n+1 vertices and at least n edges contains a cycle
• True
• False

### Question 56

Question
The length of W is the number of [blank_start]edges[blank_end] traversed
• edges
• vertices

### Question 57

Question
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.
• True
• False

### Question 58

Question
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.
• True
• False

### Question 59

Question
A walk is a path if and only if it has no repeated vertices
• True
• False

### Question 60

Question
walk is a path if and only if it has repeated vertices
• True
• False

### Question 61

Question
A closed walk is a cycle if and only if the only repeated vertex is the first and last vertex
• True
• False

### Question 62

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

### Question 63

Question
A graph G is [blank_start]connected[blank_end] if for any two vertices u and v of G there is a walk in G from u to v.
• connected

### Question 64

Question
A [blank_start]connected component[blank_end] of G is a maximal connected subgraph of G
• connected component
• component
• subgraph
• tree
• cycle

### Question 65

Question
A tree is a [blank_start]connected[blank_end] [blank_start]acyclic[blank_end] graph.
• connected
• component
• walk
• path
• unconnected
• join
• acyclic
• walks
• paths
• cyclic

### Question 66

Question
A [blank_start]leaf[blank_end] of a tree is a vertex v with d(v) = [blank_start]1[blank_end].
• leaf
• edge
• vertex
• 1
• 2
• 0
• 5

### Question 67

Question
Any tree on n ≥ 2 vertices has a leaf.
• True
• False

### Question 68

Question
Any tree on n ≥ 0 vertices has a leaf.
• True
• False

### Question 69

Question
Any connected graph contains a spanning tree
• True
• False

### Question 70

Question
Any connected graph on n vertices with precisely n − 1 edges is a tree
• True
• False

### Question 71

Question
Any connected graph on n vertices with precisely n edges is a tree
• True
• False

### Question 72

Question
Any acyclic graph on n vertices with precisely n − 1 edges is a tree.
• True
• False

### Question 73

Question
Any acyclic graph on n vertices with precisely n edges is a tree.
• True
• False

### Similar

How to improve your SAT math score
The SAT Math test essentials list
GCSE Maths: Pythagoras theorem
Edexcel GCSE Maths Specification - Algebra
Mathematics
Projectiles
Using GoConqr to teach Maths
FREQUENCY TABLES: MODE, MEDIAN AND MEAN
Using GoConqr to study Maths
HISTOGRAMS
Mathematics Overview