Graph Theory

Question 1

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

Accepted Answer

Vertices

Answer

Edges

Question 2

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

Accepted Answer

Edges

Answer

Vertices

Question 3

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

Accepted Answer

{a,b,c,d,e}

Question 4

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

Accepted Answer

{{a, b}, {b, c}, {a, c}, {c, d}}

Question 5

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

Answer

true

Question 6

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

Answer

true

Question 7

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.

Accepted Answer

isomorphic

Question 8

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

Accepted Answer

order

Question 9

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

Accepted Answer

vertices

Question 10

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

Accepted Answer

size

Question 11

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

Accepted Answer

edges

Question 12

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

Accepted Answer

uv

Answer

{uv}

Question 13

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

Accepted Answer

u,v

Question 14

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

Accepted Answer

incident

Answer

adjacent

Question 15

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

Accepted Answer

adjacent

Answer

incident

Question 16

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

Accepted Answer

neighbour

Question 17

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

Accepted Answer

neighbourhood

Question 18

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

Accepted Answer

neighbourhood N(v)

Answer

neighbourhood N(u)

Answer

compliment N(v)

Answer

neighbourhood G(v)

Answer

neighbourhood d(v)

Answer

neighbourhood N(G)

Question 19

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

Accepted Answer

neighbours

Question 20

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

Accepted Answer

isolated

Answer

complementary

Answer

distinct

Answer

incident

Answer

adjacent

Question 21

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

Accepted Answer

{b, c}

Question 22

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

Accepted Answer

{c}

Question 23

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

Accepted Answer

empty

Question 24

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

Accepted Answer

an isolated

Answer

an adjacent

Answer

a

Question 25

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

Accepted Answer

isolated

Question 26

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

Accepted Answer

The number of neighbours of v

Answer

The number of edges of v

Answer

The number of vertices of v

Answer

The number of v

Question 27

d(v) =

Accepted Answer

|N(v)|

Answer

|G(v)|

Answer

0

Question 28

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].

Accepted Answer

2

Accepted Answer

2

Accepted Answer

3

Accepted Answer

1

Accepted Answer

0

Question 29

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

Question 30

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].

Accepted Answer

0

Accepted Answer

n − 1

Question 31

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.

Accepted Answer

degree

Question 32

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

Answer

true

Question 33

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

Accepted Answer

twice

Question 34

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

Accepted Answer

edges

Question 35

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

Accepted Answer

degrees

Question 36

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

Answer

true

Question 37

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

Answer

true

Question 38

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

Accepted Answer

degree

Question 39

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

Accepted Answer

degree sequence

Question 40

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.

Accepted Answer

minimum degree

Accepted Answer

smallest

Question 41

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.

Accepted Answer

maximum degree

Accepted Answer

largest degree

Question 42

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

Accepted Answer

regular

Question 43

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

Answer

true

Question 44

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

Accepted Answer

k

Question 45

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

Accepted Answer

k-regular

Question 46

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.

Accepted Answer

subgraph

Question 47

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

Accepted Answer

deleting

Question 48

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

Accepted Answer

spanning

Answer

"blank"

Answer

copy

Question 49

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

Accepted Answer

subgraph

Answer

graph

Answer

spanning subgraph

Answer

copy

Question 50

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

Answer

true

Question 51

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

Answer

true

Question 52

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

Answer

true

Question 53

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

Answer

true

Question 54

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

Answer

true

Question 55

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

Answer

true

Question 56

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

Accepted Answer

edges

Answer

vertices

Question 57

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

Question 58

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

Question 59

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

Answer

true

Question 60

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

Answer

true

Question 61

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

Answer

true

Question 62

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

Answer

true

Question 63

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.

Accepted Answer

connected

Question 64

A [blank_start]connected component[blank_end] of G is a maximal connected subgraph of G

Accepted Answer

connected component

Answer

component

Answer

subgraph

Answer

tree

Answer

cycle

Graph Theory

Fragen in diesem Quiz (73)

Informationen

Feedback

Wie gefällt dir das neue Design?