Combo Midterm 3
1. In any graph, the number of vertices with an odd degree must be
a) Zero
b) Even
c) Odd
d) Equal to the number of edges
2. According to the Handshaking Lemma, the sum of the degrees of all vertices in a graph is equal to
a) The number of vertices
b) The number of edges
c) Twice the number of vertices
d) Twice the number of edges
3. A simple graph...
a) Must have fewer than 5 vertices
b) Must have no loops
c) Must be connected
d) Must be bipartite
4. If two graphs, G1 and G2, have different degree sequences, which statement is true?
a) They are guaranteed to be isomorphic
b) They are guaranteed to be planar
c) They may or may not be isomorphic
d) They are guaranteed to be non-isomorphic
5. True or false: If two graphs have the same degree sequence, they are isomorphic.
a) True
b) False
6. Cayley's Formula states that the number of labeled trees with n vertices is
a) nn-2
b) n!
c) nn
d) nn-1
7. A Prufer code for a tree with n vertices has length
a) n
b) n/2
c) n-2
d) n-1
8. True or false: Two trees with the same Prufer code are isomorphic.
a) True
b) False
9. A graph is bipartite if and only if...
a) It is an even cycle
b) It contains no odd cycles
c) It is a path
d) It contains no even cycles
10. When finding the Prufer code of a tree, which vertex is removed first?
a) Leaf with the smallest label
b) Vertex with the largest label
c) Vertex with the smallest label
d) Leaf with the largest label
11. The goal of Kruskal's and Prim's algorithms is...
a) To find the shortest path between two nodes
b) To find the chromatic number of the graph
c) To find the minimum weight spanning tree
d) To find a Hamiltonian cycle
12. Minimum spanning trees are unique...
a) If the graph is connected
b) For any graph
c) If the graph is simple
d) If the graph has distinct edge weights
13. In Kruskal's Algorithm, which rule must be followed when selecting the next edge with minimum weight?
a) It must avoid forming a cycle
b) It must be incident to the previously added edge
c) It must be connected to the root vertex
d) It must be connected to a leaf node
14. How does Prim's Algorithm select the next edge to add to the minimum spanning tree T?
a) It picks the minimum weight edge in T
b) It picks a random edge in T
c) It picks the smallest edge in the entire graph
d) It picks the minimum weight edge with one endpoint in T and the other not in T
15. In a connected planar graph with n vertices, m edges, and r faces, Euler's Formula states
a) m - n + r = 2
b) n + m - r = 2
c) n − m - r = 2
d) n − m + r = 2
16. If a simple planar graph has n ≥ 3 vertices, the number of edges m must satisfy
a) m < 3n − 6
b) m ≥ 3n − 6
c) m ≤ 3n − 6
d) m > 3n − 6
17. According to Wagner's Theorem, a graph is planar if it does not contain a minor of...
a) K5 or K3,3
b) K5 or C3
c) C5 or K3,3
d) K5 or K3
18. A minor is formed by...
a) Deleting edges and vertices and contracting vertices
b) Deleting edges and vertices and contracting edges
c) Deleting edges and vertices
d) Deleting cycles
19. Are subgraphs minors?
a) False
b) True
20. Why is K5 non-planar?
a) The number of edges exceeds 3n-6
b) It has too many vertices
c) It has odd cycles
d) It is not bipartite
21. A connected graph has an Euler Circuit if and only if
a) Every vertex has an even degree
b) It has exactly two odd degree vertices
c) Every vertex has an odd degree
d) It has no cycles
22. All Euler Circuits are Euler Trails
a) False
b) True
23. A connected graph has an Euler Trail (but not a circuit) if and only if...
a) All vertices are even
b) All vertices are odd
c) Exactly two vertices have odd degrees
d) It is a complete graph
24. A Hamiltonian cycle is a cycle that
a) Must have even length
b) Contains every edge exactly once
c) Is the shortest path between two nodes
d) Contains every vertex exactly once
25. There exists commonly known necessary and sufficient conditions for (a) Euler circuits, (b) Hamiltonian cycles
a) (a) True, (b) True
b) (a) True, (b) False
c) (a) False, (b) True
d) (a) False, (b) False
26. Dirac's Theorem states a simple graph (n ≥ 3) has a Hamiltonian cycle if every vertex v satisfies
a) d(v) ≥ 3
b) d(v) ≥ n − 1
c) d(v) ≥ n / 2
d) d(v) is even
27. By Dirac's Theorem, if a simple graph with 8 vertices has a vertex with a degree of 3, it must not have a Hamiltonian cycle.
a) False
b) True
28. The chromatic number χ(G) is defined as
a) The minimum colors needed for a vertex coloring
b) The maximum colors possible for a vertex coloring
c) The minimum colors needed for an edge coloring
d) The minimum colors needed for a proper vertex coloring
29. What is the smallest chromatic number possible for a bipartite graph with more than one vertex?
a) 0
b) 3
c) 2
d) 1
30. What is the smallest chromatic number possible for a bipartite graph with at least one edge?
a) 3
b) 1
c) 2
d) 0
31. What is the chromatic number of an odd cycle?
a) 1
b) 3
c) 0
d) 2
32. The chromatic number χ(Kn) is
a) n
b) 2
c) n - 1
d) 2n
33. The chromatic polynomial P(G,λ) helps find
a) The number of ways to color G with λ colors
b) The number of vertices
c) The number of ways to choose λ vertices from G
d) The number of ways to properly color G with λ colors
34. According to the Deletion-Contraction recursion, P(G,λ) equals...
a) P(G−e, λ) + P(G\e, λ)
b) P(G−e, λ) − P(G/e, λ)
c) P(G/e, λ) − P(G−e, λ)
d) P(G−e, λ) − P(G\e, λ)
35. Which of the following is a valid chromatic polynomial for a graph with 4 vertices?
a) λ4 - 4λ3 + 6λ2 - 3λ
b) 2λ4 - 5λ3 + 6λ2 - 3λ
c) λ4 + 4λ3 + 6λ2 + 3λ
d) λ4 - 4λ3 + 6λ2 - 4λ + 1
36. What is the value of the Ramsey number R(3,3)?
a) 6
b) 3
c) 5
d) 7
37. What is the value of the Ramsey number R(3,4)?
a) 12
b) 9
c) 17
d) 14
38. R(3, 3) = 6 implies that in any group of 6 people, there are always
a) 3 mutual friends or 3 mutual strangers
b) 3 mutual friends and 3 mutual strangers
c) A path of length 6
d) No cliques larger than 3
39. The Ramsey number R(2, n) is always equal to
a) n - 1
b) 2
c) 2n
d) n