Graph Theory

For each statement, write True or False.

(a) Every tree has exactly one perfect matching.

(b) If a connected graph G has n vertices and (G) = n/2, then it must have an Eulerian cycle.

(c) If (G) = (G), then (G) = (G).

(d) If M is a maximum matching in a connected graph, then V (M) must be a minimum vertex cover of the graph.

(e) In a connected graph on 100 vertices, any two longest paths must have a vertex in common.

(f) If a graph has an odd number of vertices, then it has an odd number of vertices of odd degree.

(g) For even n 2, if a graph has n vertices and exactly n/2 connected components, then the graph must be a matching.

(h) Every graph with minimum degree 10 must have a cycle of length at least 9.