Fall 2016

Professor: Erika L.C. King

Email:eking@hws.edu

Office: Lansing 304

Phone: (315)781-3355

**I will randomly grade about four of the entries
completely. Then I will count to see how many total entries you have. Note that it is highly likely that
the graded entries will be those things we did not specifically go over in class. Remember to follow the
journal guidelines (hightlighting exercise/problem numbers, etc.).**

- Mindscapes 8, 11, 14 and 19 from Section 3.4 (pages 186-188).
- Mindscapes 1, 2, 3, 8, 11 and 19 from Section 6.1 (pages 395-398).
- Mindscapes 6 and 7 from Section 6.1 (page 396) in your journal. Do each Mindscape as asked (they are looking for Eulerian circuits), and then complete them replacing "Euler circuit" with "Hamiltonian cycle".
- Prove or disprove the conjecture: If a graph is Eulerian, then it is Hamiltonian.
- Prove or disprove the conjecture: If a graph has the property that the degrees of all its vertices have the same parity (that is, all are even or all are odd), then the graph is Hamiltonian.
- Draw all distinct trees on four vertices. Then draw all distinct forests on four vertices. Be careful that your trees and forests are truly different; remember that it does not matter how you draw the graphs, but rather what the connections between edges and vertices actually are.
- Draw all distinct trees on six vertices.
- Carefully explain how many edges a tree with 37 vertices has. Then explain how many vertices a tree with 59 edges has.
- TREE OR NOT TREE: Show that a graph on $n$ vertices with $n-1$ edges need not be a tree. (You probably have examples of this on your secret handout.)
- COMIC QUESTION: Consider the following situation. Six comic book collectors, Alex, Bailey, Carla, Joe, Leya and Tina, met to trade comic books with each other. Each trade that took place was between only two people. After the meeting, each of the six was asked how many people he or she had traded with. The answers were 5, 4, 2, 1, 3 and 2, respectively. Model this situation with graph theory by describing what would represent each vertex and what would represent each edge in the resulting graph. You need not actually draw a graph. Then prove that at least one person is mistaken.
- THE FRIENDS QUESTION: Show that in a room with at least two people, there are at least two people who have the same number of friends in the room. (Assume that if A is B's friend, then B is also A's friend.) Hint: Make a graph model as in the previous question. Then rewrite the question in graph theoretic terms.
- MINIMAL SPANNING TREES: Minimal spanning trees have been used in areas such as biomedical image analysis, pattern recognition, weather data interpretation, fungal spore pattern analysis, and the study of particle interactions in turbulent fluid flows. Research some past or current applications of minimal spanning trees online. Then, in your journal, jot down a report (roughly the equivalent of one typed page; or type a page and staple it into your journal) that describes an application of interest to you.
- Draw a graph on eight vertices with twelve edges. (a) How many edges must you eliminate to form a tree? Explain. (b) Draw at least three spanning trees of your graph. (c) How many edges does the complement of your graph have? Explain. (d) Draw the complement of your graph.
- Mindscapes 6, 10, 11 and 13 from Section 6.4 (pages 450-452).
- Consider the following. Let $G$ be a graph on nine vertices and let $v$ be a vertex of degree four. What is the degree of $v$ in the complement of $G$, $\overline{G}$? Explain.
- Consider the following. Let $G$ be a graph and let $v$ be a vertex such that the degree of $v$ is six in $G$ and seven in $\overline{G}$. How many vertices are in $G$? Explain.
- Consider the following. Let $G$ be a graph on 12 vertices with 24 edges. How many edges are in $\overline{G}$? Explain.
- Mindscapes 6, 9, 10, 12, 13, 15 and 26 from Section 6.2 (pages 409-411).