Quiz
Graph Theory
This quiz has question types that open in the usual player.
Questions in this quiz (73)
1What is the formal name for the points on a graph?
- AVertices
- BEdges
2What is the formal name for the lines connecting the points on a graph?
- AVertices
- BEdges
3V = [blank_start]{a,b,c,d,e}[blank_end]
- A{a,b,c,d,e}
4E = [blank_start]{{a, b}, {b, c}, {a, c}, {c, d}}[blank_end]
- A{{a, b}, {b, c}, {a, c}, {c, d}}
5Two graphs are equal if and only if they have the same vertices and the same edges.
- ATrue
- BFalse
6Two graphs are equal if and only if they have some vertices and the same edges.
- ATrue
- BFalse
7We say that two graphs G and H are [blank_start]isomorphic[blank_end] if we can relabel the vertices of G to obtain H.
- Aisomorphic
8The [blank_start]order[blank_end] of a graph G is the number of vertices of G
- Aorder
9The order of a graph G is the number of [blank_start]vertices[blank_end] of G
- Avertices
10The [blank_start]size[blank_end] of G is the number of edges of G
- Asize
11The size of G is the number of [blank_start]edges[blank_end] of G
- Aedges
12We often write [blank_start]uv[blank_end] as shorthand for an edge {u,v}
- Auv
- B{uv}
13We often write uv as shorthand for an edge {[blank_start]u, v[blank_end]}
- Au,v
14We say that an edge e = uv is [blank_start]incident[blank_end] to the vertices u and v.
- Aincident
- Badjacent
15If uv is an edge, we say that the vertices u and v are [blank_start]adjacent[blank_end]
- Aadjacent
- Bincident
16u is a [blank_start]neighbour[blank_end] of v and that v is a neighbour of u.
- Aneighbour
17For any vertex v of a graph G, the [blank_start]neighbourhood[blank_end] N(v) of v is the set of neighbours of v
- Aneighbourhood
18For any vertex v of a graph G, the ............. of v is the set of neighbours of v
- Aneighbourhood N(v)
- Bneighbourhood N(u)
- Ccompliment N(v)
- Dneighbourhood G(v)
- Eneighbourhood d(v)
- Fneighbourhood N(G)
19We say that v is isolated if it has no [blank_start]neighbours[blank_end].
- Aneighbours
20We say that v is [blank_start]isolated[blank_end] if it has no neighbours.
- Aisolated
- Bcomplementary
- Cdistinct
- Dincident
- Eadjacent
21The neighbourhood of a is N(a) = [blank_start]{b, c}[blank_end]
- A{b, c}
22The neighbourhood of d is N (d) = [blank_start]{c}[blank_end]
- A{c}
23The neighbourhood of e is N(e) = [blank_start]empty[blank_end]
- Aempty
24Vertex e is ........ vertex
- Aan isolated
- Ban adjacent
- Ca
25Vertex e is an [blank_start]isolated[blank_end] vertex
- Aisolated
26The degree of a vertex v in a graph G is d(v) = |N(v)|, that is,
- AThe number of neighbours of v
- BThe number of edges of v
- CThe number of vertices of v
- DThe number of v
27d(v) =
- A|N(v)|
- B|G(v)|
- C0
28The 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].
- A2
- B2
- C3
- D1
- E0
29If G is a graph with n vertices, then the degree of each vertex of G is an integer between 0 and n − 1.
- ATrue
- BFalse
30If 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].
- A0
- Bn − 1
31If 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.
- Adegree
32The sum of all vertex degrees is twice the number of edges
- ATrue
- BFalse
33the sum of all vertex degrees is [blank_start]twice[blank_end] the number of edges
- Atwice
34The sum of all vertex degrees is twice the number of [blank_start]edges[blank_end]
- Aedges
35The sum of all vertex [blank_start]degrees[blank_end] is twice the number of edges
- Adegrees
36In any graph there are an even number of vertices with odd degree.
- ATrue
- BFalse
37In any graph there are an even number of edges with odd degree.
- ATrue
- BFalse
38Any graph on at least two vertices has two vertices of the same [blank_start]degree[blank_end].
- Adegree
39The [blank_start]degree sequence[blank_end] of a graph G is the sequence of all degrees of vertices in G
- Adegree sequence
40The [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.
- Aminimum degree
- Bsmallest
41The [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.
- Amaximum degree
- Blargest degree
42A graph G is [blank_start]regular[blank_end] if every vertex of G has the same degree
- Aregular
43We say that G is k-regular to mean that every vertex has degree k.
- ATrue
- BFalse
44We say that G is [blank_start]k[blank_end]-regular to mean that every vertex has degree k.
- Ak
45We say that G is [blank_start]k-regular[blank_end] to mean that every vertex has degree k.
- Ak-regular
46A 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.
- Asubgraph
47A 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
- Adeleting
48H is a [blank_start]spanning[blank_end] subgraph of G if additionally V (H) = V (G), that is, if only edges were deleted.
- Aspanning
- B"blank"
- Ccopy
49H is a [blank_start]subgraph[blank_end] of a graph G if we can obtain H by deleting vertices and edges of G.
- Asubgraph
- Bgraph
- Cspanning subgraph
- Dcopy
50Let G be a graph with δ(G) ≥ 2. Then G contains a cycle.
- ATrue
- BFalse
51Let G be a graph with δ(G) ≥ 0. Then G contains a cycle.
- ATrue
- BFalse
52Let G be a graph with N(G) ≥ 2. Then G contains a cycle.
- ATrue
- BFalse
53Any graph with n vertices and at least n edges contains a cycle
- ATrue
- BFalse
54Any graph with n vertices and at least n-1 edges contains a cycle
- ATrue
- BFalse
55Any graph with n+1 vertices and at least n edges contains a cycle
- ATrue
- BFalse
56The length of W is the number of [blank_start]edges[blank_end] traversed
- Aedges
- Bvertices
57A 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.
- ATrue
- BFalse
58A 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.
- ATrue
- BFalse
59A walk is a path if and only if it has no repeated vertices
- ATrue
- BFalse
60walk is a path if and only if it has repeated vertices
- ATrue
- BFalse
61A closed walk is a cycle if and only if the only repeated vertex is the first and last vertex
- ATrue
- BFalse
62A closed walk is a cycle if and only if there is a repeated vertex at the first and last vertex
- ATrue
- BFalse
63A 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.
- Aconnected
64A [blank_start]connected component[blank_end] of G is a maximal connected subgraph of G
- Aconnected component
- Bcomponent
- Csubgraph
- Dtree
- Ecycle
65A tree is a [blank_start]connected[blank_end] [blank_start]acyclic[blank_end] graph.
- Aconnected
- Bcomponent
- Cwalk
- Dpath
- Eunconnected
- Fjoin
- Gacyclic
- Hwalks
- Ipaths
- Jcyclic
66A [blank_start]leaf[blank_end] of a tree is a vertex v with d(v) = [blank_start]1[blank_end].
- Aleaf
- Bedge
- Cvertex
- D1
- E2
- F0
- G5
67Any tree on n ≥ 2 vertices has a leaf.
- ATrue
- BFalse
68Any tree on n ≥ 0 vertices has a leaf.
- ATrue
- BFalse
69Any connected graph contains a spanning tree
- ATrue
- BFalse
70Any connected graph on n vertices with precisely n − 1 edges is a tree
- ATrue
- BFalse
71Any connected graph on n vertices with precisely n edges is a tree
- ATrue
- BFalse
72Any acyclic graph on n vertices with precisely n − 1 edges is a tree.
- ATrue
- BFalse
73Any acyclic graph on n vertices with precisely n edges is a tree.
- ATrue
- BFalse
Information
- Description
- Bachelors Degree Mathematics Quiz on Graph Theory, created by Will Rickard on 04/01/2016.
- Author
- Will Rickard
- Language
- English
- Views
- 1,253
- Tags
- Rating
- No ratings yet Rate this quiz