Final

Question 1

Let A and B be sets. Give the definition of A and B having the same cardinality

Answer 1

The sets A and B have the same cardinality if there exists a bijection f : A → B

Question 2

Give the definition of a k–to–1 correspondence.

Answer 2

A function f : A → B is a k–to–1 correspondence if, for every y ∈ B, there exist exactly
k–many elements x ∈ A for which f (x) = y.

Question 3

Give the definition of a permutation.

Answer 3

A permutation is a bijection from {1, . . . , n} to itself, for some nonzero n ∈ N

Question 4

Give the definition of an r–permutation on a set S.

Answer 4

An r–permutation on a set S is an injective function f : {1, . . . , r} → S

Question 5

Give the definition of an r–subset of a set S

Answer 5

An r–subset of S is a subset of S which contains r elements

Question 6

State the pigeonhole principle.

Answer 6

Consider f : A → B where A and B are finite sets. If |A| > |B| then there are two
elements in A which map to the same element of B under f

Question 7

Give the definition of a finite simple graph.

Answer 7

A finite simple graph is a pair (V, E) where V is a finite set of vertices and E is a set
of 2–subsets of V called edges

Question 8

Let G be a graph with vertices a and b and edge e. Give the definition of a and b being endpoints
of e

Answer 8

a and b are endpoints of e if e = {a, b}.

Question 9

Let G be a graph with vertices a and b and edge e. Give the definition of e being incident to a and
b.

Answer 9

e is incident to a and b if e = {a, b}

Question 10

Let G be a graph with vertices a and b. Give the definition of a and b being adjacent.

Answer 10

a and b are adjacent if they are the endpoints of a common edge

Question 11

Let G be a graph and let v be a vertex of G. Give the definition of the degree of v

Answer 11

The degree of v is the number of edges incident to v

Question 12

Give the definition of a subgraph.

Answer 12

Let G = (V, E) and H = (W, F ) be graphs. We say that H is a subgraph of G if
W ⊆ V and F ⊆ E

Question 13

Let G be a graph. Give the definition of a walk in G

Answer 13

A walk in G is a sequence of vertices for which each vertex is adjacent to the preceding
vertex.

Question 14

Give the definition of a path.

Answer 14

A path is a walk without repeated vertices.

Question 15

Let G be a graph and let v and w be vertices of G. Give the definition of v and w being connected

Answer 15

v and w are connected if there exists a path between them

Question 16

Let G be a graph and let S be a subset of vertices of G. Give the definition of S being connected

Answer 16

S is connected if all of its vertices are pairwise connected

Question 17

Give the definition of a disconnected graph.

Answer 17

A disconnected graph is a graph which is not connected.

Question 18

Give the definition of a connected component of a graph G

Answer 18

A connected component of a graph G is a connected subgraph which is not part of any
larger connected subgraph

Question 19

Give the definition of a cycle.

Answer 19

A cycle is a walk without repeated vertices, except the first and last vertices which must
coincide

Question 20

Give the definition of a trail.

Answer 20

A trail is a walk without repeated edges.

Question 21

Give the definition of a circuit.

Answer 21

A circuit is a trail whose first and last vertices coincide.

Question 22

Give the definition of an Eulerian trail.

Answer 22

An Eulerian trail is a trail passing through every edge.

Question 23

Give the definition of an Eulerian circuit.

Answer 23

An Eulerian circuit is a circuit passing through every edge.

Question 24

Give the definition of a tree.

Answer 24

A tree is a connected graph without cycles.

Question 25

Let G be a graph. Give the definition of a spanning tree of G

Answer 25

A spanning tree of G is a subgraph of G which contains all of its vertices and which is
a tree.

Question 26

Give the definition of a weighted graph.

Answer 26

A weighted graph is a triple (V, E, w) where (V, E) is a graph and w is a function from
E to R called a weight function.

Question 27

Let H be a subgraph of a weighted graph G = (V, E, w). Give the definition of the weight of H

Answer 27

see quiz 10 question 4

Question 28

Let G be a weighted graph. Give the definition of a minimal spanning tree of G

Answer 28

A minimal spanning tree of G is a spanning tree T of G such that, for every spanning
tree T ′ of G, weight (T ) ⩽ weight (T ′)