Graph algorithm

Graph G with 10 vertices has 4 pair-wise nonadjacent vertices. Minimum vertex cover of G has a. at least 4 vertices Yes No Don't know b. at most 6 vertices Yes No Don't know The Minimum Spanning Tree of a connected weighted graph with 100 edges always a. contains the least weight edge Yes No Don't know b. contains 2 least weight edges Yes No Don't know c. contains 3 least weight edges Yes No Don't know d. has at least 16 edges Yes No Don't know e. has at least 15 edges Yes No Don't know The Single-source Shortest-Path Tree of a edge-positive-weighted graph always a. contains the least weight edge Yes No Don't know b. contains the least weight edge from source Yes No Don't know c. no shorter than MST Yes No Don't know (4) The number of different perfect matchings for 6 points in the plane is no less than 10 Yes No Don't know no more than 15 Yes No Don't know The fastest algorithm finding a negative cycle in a weighted graph has runtime _____ The fastest algorithm finding a cycle in graph has runtime _____ (7) A planar graph G has 5 vertices and 7 edges, the # of faces in the dual graph G' is _____