Graph Theory

(7) For each statement, write True or False next to it in the righthand column of the table, depending on whether it's true or false. For this problem, you do not need to show your work or give an explanation; just give an answer True/False for each part. (a) Every tree has exactly one perfect matching. (b) If a connected graph G has n vertices and 6(G) = n/2, then it must have an Eulerian cycle. (c) If *(G) = 6(G), then A(G) = k(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 2, if a graph has n vertices and exactly n/2 con- nected components, then the graph must be a matching. (h) Every graph with minimum degree 10 must have a cycle of length at least 9