Math 225 Exam 3 Review

1234567891011121314151617181920212223242526272829303132333435
Across
  1. 5. (Thm.) Trees contain no _______
  2. 8. Whose theorem states that a graph G is planar if and only if G does not contain a subgraph which is either a K_5 or K_3,3 configuration
  3. 9. (Thm.) For any tree T=(V,E), the number of edges is...
  4. 11. A ______ ______ (space omitted in puzzle) is a closed Hamiltonian Path
  5. 12. (Thm.) For any connected planar graph G with |V|>=3, we have...
  6. 13. A graph is _______ if it has a Hamiltonian Circuit
  7. 15. A graph G is ______ if it can be drawn in a two-dimensional plane with no edges crossing
  8. 16. The degree of every vertex in an Euler Cycle must be ______
  9. 18. The "3|V|-6" Theorem ______ be used to prove that a graph is planar
  10. 23. A ______ ______ (space omitted in puzzle) of a graph G is a way to color its vertices so that adjacent vertices are different colors
  11. 24. An ______ ______ (space omitted in puzzle) in a multigraph G is a sequence of adjacent vertices in G using every edge of G exactly once
  12. 26. An Euler Trail can have exactly ______ vertices of odd degree
  13. 27. A ______ is a vertex of degree one
  14. 30. ______ ______ (space omitted in puzzle) are a way to transmit a sequence of numbers using only 0s and 1s in a way which minimizes the effect of single bit errors
  15. 31. The _______ Condition can be used to prove that a graph IS Hamiltonian
  16. 32. The sum of the _______ of all vertices in a graph is equal to 2|E|
  17. 34. In a _______ graph, the vertices can be divided into two disjoint sets
  18. 35. An ______ subgraph H=(V',E') of G=(V,E) has includes all possible edges in E that have both endpoints in V'
Down
  1. 1. The number of edges in the complement of a graph G = (V,E) is ______
  2. 2. (Thm.) All trees with at least two vertices have _______
  3. 3. (Thm.) For any planar graph G with |V|>=3 and no triangles, we have...
  4. 4. A _______ is a graph where multiple edges are allowed between any two vertices and also loops (edges from a vertex to itself) are allowed
  5. 6. The number of colors necessary to execute a proper coloring of a graph G is a _______
  6. 7. A ______ ______ (space omitted in puzzle) in a graph G is a path of edges in G which includes every vertex in G
  7. 10. Euler's Polyhedral Formula states...
  8. 14. By the ______ ______ (space omitted in puzzle), if T is a tree and v is a leaf of T, then T-v is also a tree
  9. 17. Two graphs are ______ is they contain the same number of vertices which are connected in the same way
  10. 19. A ______ is a connected graph (with at least one vertex) which has no cycles.
  11. 20. An ______ ______ (space omitted in puzzle) is a closed Euler Trail
  12. 21. The ______ of a graph G has all the same vertices but the complementary set of edges
  13. 22. The Necessary Condition states that the number of _______ in G-S<=|S|
  14. 25. The sum of the degree of all ______ in a graph is equal to 2|E|
  15. 28. The Sufficient Condition states that, for two non-adjacent vertices v and w in G, deg(v)+deg(w) is greater than or equal to the ______ of vertices in G
  16. 29. The _______ Condition can be used to prove that a graph is NOT Hamiltonian
  17. 33. A graph is _______ if it has an Euler Cycle