Final Flashcards
Let A and B be sets. Give the definition of A and B having the same cardinality
The sets A and B have the same cardinality if there exists a bijection f : A → B
Give the definition of a k–to–1 correspondence.
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.
Give the definition of a permutation.
A permutation is a bijection from {1, . . . , n} to itself, for some nonzero n ∈ N
Give the definition of an r–permutation on a set S.
An r–permutation on a set S is an injective function f : {1, . . . , r} → S
Give the definition of an r–subset of a set S
An r–subset of S is a subset of S which contains r elements
State the pigeonhole principle.
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
Give the definition of a finite simple graph.
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
Let G be a graph with vertices a and b and edge e. Give the definition of a and b being endpoints
of e
a and b are endpoints of e if e = {a, b}.
Let G be a graph with vertices a and b and edge e. Give the definition of e being incident to a and
b.
e is incident to a and b if e = {a, b}
Let G be a graph with vertices a and b. Give the definition of a and b being adjacent.
a and b are adjacent if they are the endpoints of a common edge
Let G be a graph and let v be a vertex of G. Give the definition of the degree of v
The degree of v is the number of edges incident to v
Give the definition of a subgraph.
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
Let G be a graph. Give the definition of a walk in G
A walk in G is a sequence of vertices for which each vertex is adjacent to the preceding
vertex.
Give the definition of a path.
A path is a walk without repeated vertices.
Let G be a graph and let v and w be vertices of G. Give the definition of v and w being connected
v and w are connected if there exists a path between them
Let G be a graph and let S be a subset of vertices of G. Give the definition of S being connected
S is connected if all of its vertices are pairwise connected
Give the definition of a disconnected graph.
A disconnected graph is a graph which is not connected.
Give the definition of a connected component of a graph G
A connected component of a graph G is a connected subgraph which is not part of any
larger connected subgraph
Give the definition of a cycle.
A cycle is a walk without repeated vertices, except the first and last vertices which must
coincide
Give the definition of a trail.
A trail is a walk without repeated edges.
Give the definition of a circuit.
A circuit is a trail whose first and last vertices coincide.
Give the definition of an Eulerian trail.
An Eulerian trail is a trail passing through every edge.
Give the definition of an Eulerian circuit.
An Eulerian circuit is a circuit passing through every edge.
Give the definition of a tree.
A tree is a connected graph without cycles.
Let G be a graph. Give the definition of a spanning tree of G
A spanning tree of G is a subgraph of G which contains all of its vertices and which is
a tree.
Give the definition of a weighted graph.
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.
Let H be a subgraph of a weighted graph G = (V, E, w). Give the definition of the weight of H
see quiz 10 question 4
Let G be a weighted graph. Give the definition of a minimal spanning tree of G
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 ′)
