Let G be ___________________ graph. A spanning tree T of G is a subgraph such that ___________________.___________________ has a spanning tree. If the edges of G are weighted, we say T is a minimum spanning tree of G if ___________________. There ___________________.

Fill in the blanks from the following options:

(1) a directed

(1) an undirected

(2) T is a tree and V(G) = V(T)

(2) G[V(T)] is a tree.

(3) Every graph

(3) Every connected graph

(3) Not every connected graph

(4) T contains as few edges as possible.

(4) the edges of T have as little total weight as possible.

(5) is exactly one minimum spanning tree of G

(5) is exactly one minimum spanning tree of G (counting isomorphic trees as the same)

(5) could be multiple minimum spanning trees of G

Match the words to their definitions.

Matching ___________________

Perfect matching ___________________

Maximum matching ___________________

Bipartite graph ___________________

Bipartition of a graph G ___________________

Augmenting path of a graph G with respect to a matching ___________________

A. A graph whose vertex set can be partitioned into two sets A and B which each contain no edges

B. A collection of disjoint edges which is as large as possible

C. A collection of disjoint edges which covers every vertex in the graph

D. A pair (A, B) of disjoint sets with V(G) = A U B such that neither A nor B contain any edges of G.

E. A collection of disjoint edges

F. A path in G which alternates between matching and non-matching edges, and which begins and ends with unmatched vertices.