Section 2: Trees

Question 1

Cycle in a graph G

Answer 1

a subgraph of G isomorphic to Ck
for some k ≥ 3.

Question 2

Forest

Answer 2

a graph that contains no cycles

Question 3

Tree

Answer 3

connected acyclic graph

Question 4

Spanning tree for a connected graph G

Answer 4

a spanning subgraph of G that is a tree

Question 5

Spanning forest

Answer 5

a subgraph of G that is a forest

Question 6

Cayley’s Formula

Answer 6

A complete graph with n vertices
has n^(n−2) (labelled) spanning trees.

Question 7

Kruskal’s Algorithm

Answer 7

a) Set T = (V, ∅).
b) Let E’ be the subset of edges e ∈ E such that
* e is not already in T, and
* adding e to T does not create a cycle;
add to T the edge in E’
that has the smallest weight.
c) If T is not connected, go to step 2.
d) Output T.

Question 8

Theorem about Kruskal’s algorithm

Answer 8

Given any weighted connected graph G = (V, E) as input, Kruskal’s algorithm will output a spanning tree of minimum weight

Question 9

Prim’s Algorithm

Answer 9

a) Set T = (V, ∅).
b) Add an edge of minimum weight to T.
c) Let E’ be the subset of edges e in E such that
* e is not already in T,
* adding e to T does not create a cycle, and
* e is incident with an edge already in T;
add to T the edge in E’
that has the smallest weight.
d) If T is not connected, go to step 3.
e) Output T.