Graph Theory

Will Rickard
Quiz by Will Rickard, updated more than 1 year ago
Will Rickard
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.
Tags

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]
Answer
  • {a,b,c,d,e}

Question 4

Question
E = [blank_start]{{a, b}, {b, c}, {a, c}, {c, d}}[blank_end]
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]
Answer
  • {b, c}

Question 22

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

Question 23

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

Question 24

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

Question 25

Question
Vertex e is an [blank_start]isolated[blank_end] vertex
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].
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

Similar

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