Final exan Problem 3. [10 points] Circle either true or false next to each statement below. Assume graphs are undirected without self-loops or multi-edges 1. For all n > 3, the complete graph on n vertices has an Euler false 2. If a graph contains no odd-length cycle, then it is bipartite true 3. Every non-bipartite graph contains a 3-cycle as a subgraph false 4. Every graph with a Hamiltonian cycle also has an Euler tour 5. There exists a graph with 20 vertices, 10 edges, and 5 con- false nected component 6. Every connected graph has a tree as a subgraph true 7. In every planar embedding of a connected planar graph, the true number of vertices plus the number of faces is greater than the number of edges 8. If every girl likes at least 2 boys, then every girl can be false matched with a boy she likes 9. If every vertex in a graph has degree 3, then the graph is 4-true colorable 10. There exists a six-vertex graph with vertex degrees 0, 1, 2, 3, false 4, and 5Final Exam 4 Problem 3. [10 points] Circle either true or false next to each statement below. Assume graphs are undirected without self­loops or multi­edges. 1. For all n ≥ 3, the complete graph on n vertices has an Euler false tour. 2. If a graph contains no odd­length cycle, then it is bipartite. true 3. Every non­bipartite graph contains a 3­cycle as a subgraph. false 4. Every graph with a Hamiltonian cycle also has an Euler tour. false 5. There exists a graph with 20 vertices, 10 edges, and 5 con­ false nected components. 6. Every connected graph has a tree as a subgraph. true 7. In every planar embedding of a connected planar graph, the true number of vertices plus the number of faces is greater than the number of edges. 8. If every girl likes at least 2 boys, then every girl can be false matched with a boy she likes. 9. If every vertex in a graph has degree 3, then the graph is 4­ true colorable. 10. There exists a six­vertex graph with vertex degrees 0, 1, 2, 3, false 4, and 5