Problem 13
Show that in a simple planar graph with no triangles, \(e \leq 2 v-4\).
Problem 14
The Hamiltonian path problem is the problem of determining whether a graph has a Hamiltonian path. Explain why this problem is in NP. Explain why the problem of determining whether a graph has a Hamiltonian path is NP-complete.
Problem 14
Show that in a simple bipartite planar graph, \(e \leq 2 v-4\). Use this fact to prove that \(K_{3,3}\) is not planar.
Problem 14
Let \(G\) be a connected graph with no odd cycles. Let \(x\) be a vertex of \(G\). Let \(X\) be all vertices at an even distance from \(x\), and let \(Y\) be all vertices at an odd distance from \(x\). Prove that \(G\) is bipartite with parts \(X\) and \(Y\).
Problem 14
Are there graphs with \(v\) vertices and \(v-1\) edges and no cycles that are not trees? Give a proof to justify your answer.
Problem 15
What is the sum of the maximum size of an independent set and the minimum size of a vertex cover in a graph \(G\) ? (Hint: It is useful to think both about the independent set and its complement relative to the vertex set.)
Problem 15
Suppose that a graph \(G\) is connected, but, for each edge, deleting that edge leaves a disconnected graph. What can you say about \(G\) ? Prove it.
Problem 15
Show that in a simple planar graph with no triangles, there is a vertex of degree 3 or less.
Problem 16
Show that if a simple planar graph has fewer than 12 vertices, then it has at least one vertex of degree 4 or less.
Problem 17
Draw the minimum number of drawings of trees possible so that each tree with five vertices has one of those drawings. Explain why you have drawn all possible trees.
