Across
- 5. (Thm.) Trees contain no _______
- 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
- 9. (Thm.) For any tree T=(V,E), the number of edges is...
- 11. A ______ ______ (space omitted in puzzle) is a closed Hamiltonian Path
- 12. (Thm.) For any connected planar graph G with |V|>=3, we have...
- 13. A graph is _______ if it has a Hamiltonian Circuit
- 15. A graph G is ______ if it can be drawn in a two-dimensional plane with no edges crossing
- 16. The degree of every vertex in an Euler Cycle must be ______
- 18. The "3|V|-6" Theorem ______ be used to prove that a graph is planar
- 23. A ______ ______ (space omitted in puzzle) of a graph G is a way to color its vertices so that adjacent vertices are different colors
- 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
- 26. An Euler Trail can have exactly ______ vertices of odd degree
- 27. A ______ is a vertex of degree one
- 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
- 31. The _______ Condition can be used to prove that a graph IS Hamiltonian
- 32. The sum of the _______ of all vertices in a graph is equal to 2|E|
- 34. In a _______ graph, the vertices can be divided into two disjoint sets
- 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. The number of edges in the complement of a graph G = (V,E) is ______
- 2. (Thm.) All trees with at least two vertices have _______
- 3. (Thm.) For any planar graph G with |V|>=3 and no triangles, we have...
- 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
- 6. The number of colors necessary to execute a proper coloring of a graph G is a _______
- 7. A ______ ______ (space omitted in puzzle) in a graph G is a path of edges in G which includes every vertex in G
- 10. Euler's Polyhedral Formula states...
- 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
- 17. Two graphs are ______ is they contain the same number of vertices which are connected in the same way
- 19. A ______ is a connected graph (with at least one vertex) which has no cycles.
- 20. An ______ ______ (space omitted in puzzle) is a closed Euler Trail
- 21. The ______ of a graph G has all the same vertices but the complementary set of edges
- 22. The Necessary Condition states that the number of _______ in G-S<=|S|
- 25. The sum of the degree of all ______ in a graph is equal to 2|E|
- 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
- 29. The _______ Condition can be used to prove that a graph is NOT Hamiltonian
- 33. A graph is _______ if it has an Euler Cycle