Copy and Edit

Graph Theory

Description

Bachelors Degree Mathematics Quiz on Graph Theory, created by Will Rickard on 04/01/2016.
Will Rickard
Quiz by Will Rickard, updated more than 1 year ago
Will Rickard
Created by Will Rickard over 8 years ago
1021
3
0

Resource summary

Question 1

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

Question 2

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

Question 3

Question
V = [blank_start]{a,b,c,d,e}[blank_end]
Image:
8601080e-4ac1-46a4-a518-2f46c68bbd24 (image/png)
Answer
  • {a,b,c,d,e}

Question 4

Question
E = [blank_start]{{a, b}, {b, c}, {a, c}, {c, d}}[blank_end]
Image:
c8d7b132-a83f-4966-890c-2c87f80fbb04 (image/png)
Answer
  • {{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.
Answer
  • True
  • False

Question 6

Question
Two graphs are equal if and only if they have some vertices and the same edges.
Answer
  • 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.
Answer
  • isomorphic

Question 8

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

Question 9

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

Question 10

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

Question 11

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

Question 12

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

Question 13

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

Question 14

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

Question 15

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

Question 16

Question
u is a [blank_start]neighbour[blank_end] of v and that v is a neighbour of u.
Answer
  • 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
Answer
  • neighbourhood

Question 18

Question
For any vertex v of a graph G, the ............. of v is the set of neighbours of v
Answer
  • 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].
Answer
  • neighbours

Question 20

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

Question 21

Question
The neighbourhood of a is N(a) = [blank_start]{b, c}[blank_end]
Image:
914669cb-39e5-4fdc-bd1c-4e33eafcc3c8 (image/png)
Answer
  • {b, c}

Question 22

Question
The neighbourhood of d is N (d) = [blank_start]{c}[blank_end]
Image:
96acf762-2531-4fd5-91f5-d5bd93d89a25 (image/png)
Answer
  • {c}

Question 23

Question
The neighbourhood of e is N(e) = [blank_start]empty[blank_end]
Image:
583ad28f-1530-427c-9bc5-55b56cc39fe2 (image/png)
Answer
  • empty

Question 24

Question
Vertex e is ........ vertex
Image:
fa048c8d-c810-436b-979d-82ed500c80fd (image/png)
Answer
  • an isolated
  • an adjacent
  • a

Question 25

Question
Vertex e is an [blank_start]isolated[blank_end] vertex
Image:
5404169b-468d-4e9e-9dcb-bcb8294a00a8 (image/png)
Answer
  • isolated

Question 26

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

Question 27

Question
d(v) =
Answer
  • |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].
Image:
b8c80799-fb3f-4cdd-b777-014f83e16066 (image/png)
Answer
  • 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.
Answer
  • 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].
Answer
  • 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.
Answer
  • degree

Question 32

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

Question 33

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

Question 34

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

Question 35

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

Question 36

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

Question 37

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

Question 38

Question
Any graph on at least two vertices has two vertices of the same [blank_start]degree[blank_end].
Answer
  • 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
Answer
  • 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.
Answer
  • 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.
Answer
  • 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
Answer
  • regular

Question 43

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

Question 44

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

Question 45

Question
We say that G is [blank_start]k-regular[blank_end] to mean that every vertex has degree k.
Answer
  • 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.
Answer
  • 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
Answer
  • 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.
Answer
  • 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.
Answer
  • subgraph
  • graph
  • spanning subgraph
  • copy

Question 50

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

Question 51

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

Question 52

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

Question 53

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

Question 54

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

Question 55

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

Question 56

Question
The length of W is the number of [blank_start]edges[blank_end] traversed
Answer
  • 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.
Answer
  • 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.
Answer
  • True
  • False

Question 59

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

Question 60

Question
walk is a path if and only if it has repeated vertices
Answer
  • 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
Answer
  • 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
Answer
  • 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.
Answer
  • connected

Question 64

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

Question 65

Question
A tree is a [blank_start]connected[blank_end] [blank_start]acyclic[blank_end] graph.
Answer
  • 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].
Answer
  • leaf
  • edge
  • vertex
  • 1
  • 2
  • 0
  • 5

Question 67

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

Question 68

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

Question 69

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

Question 70

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

Question 71

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

Question 72

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

Question 73

Question
Any acyclic graph on n vertices with precisely n edges is a tree.
Answer
  • True
  • False
Show full summary Hide full summary

Want to create your own Quizzes for free with GoConqr? Learn more.

Similar

The SAT Math test essentials list
lizcortland
How to improve your SAT math score
Brad Hegarty
GCSE Maths: Pythagoras theorem
Landon Valencia
Edexcel GCSE Maths Specification - Algebra
Charlie Turner
Mathematics
Corey Lance
Projectiles
Alex Burden
Mathematics Overview
PatrickNoonan
MODE, MEDIAN, MEAN, AND RANGE
Elliot O'Leary
FREQUENCY TABLES: MODE, MEDIAN AND MEAN
Elliot O'Leary
HISTOGRAMS
Elliot O'Leary
CUMULATIVE FREQUENCY DIAGRAMS
Elliot O'Leary
Browse Library