CS 223 Assignment due 4/18/01

To disprove a statement of the form "if P then Q", you need to provide a counter-example. That is, you find something for which P is true, but Q is false. For example, the first statement below (which is false) has P = "G has N vertices and at least N-1 edges" and Q = "G is connected." Your job is to find a particular graph with N vertices (any N will do) and at least N-1 edges that is not connected. Such a graph would make P true but Q false, thus disproving "P ==> Q".

Have fun.

1. Prove or disprove the following statement: If a graph G has N vertices and at least N-1 edges, then the graph is connected.

2. Given V = {A,B,C}, how many different graphs are there with vertex set V? Draw them. (Note that by saying "graph," I am excluding digraphs, multi-graphs, and loops. On the other hand, non-connected graphs are included.)

3. How many different 4-vertex graphs are there?

4. How many different N-vertex graphs are there? Explain why.

5. How many different N-vertex digraphs without loops are there? Explain why.

6. Prove or disprove: Suppose D is a digraph, and G is the underlying graph (i.e. G is D with the arrow heads removed from the edges). If G is connected, then D is weakly connected.

7. Prove or disprove: If a graph has two vertices with odd degree and all other vertices have even degree, then the graph contains an Eulerian circuit.

8. Prove or disprove: any N-vertex free tree (see page 210) has exactly N - 1 edges.

9. Prove or disprove: every graph is 5-colorable.

10. Prove or disprove: every weighted graph has exactly one minimum spanning tree.

11. Do problem 2 on page 247.

12. You can think of polyhedral solids like a cube or a tetrahedron as graphs. So the cube, for example, is a graph with 8 vertices and 12 edges. You can construct the dual graph D of a polyhedron by putting a vertex of D in the middle of every face of the polyhedron, and connecting vertices of D only if the corresponding faces share an edge.

    Draw the cube's graph on a sheet of paper with no edge crossings. Do the same for the cube's dual graph, the tetrahedron, the tetrahedron's dual graph, the octohedron, and the octohedron's dual graph (don't know what an octohedron is? find someone who plays Dungeons and Dragons to show you an 8-sided die, or come to class Monday and ask me).

    What can you say about the duals of the octohedron, the cube, and the tetrahedron? Aren't you glad I didn't ask you about the dodecahedron (12 sides) and the icosahedron (20)?

13. Draw your favorite 10-sided polygon. Show two different triangulations of your polygon.

14. In class on Friday, I claimed that any triangulation of a polygon can be three-colored. Now suppose we consider "holey polygons" (for example, the floorplan of a house with an interior courtyard). Is it true that all triangulations of holey polygons (no Batman and Robin jokes, please) can be 3-colored? Why not?

15. Use the Two-Ears theorem and mathematical induction to prove that any triangulation of a polygon can be 3-colored. I will describe the Two-Ears theorem in class Monday 4/16.