91Ó°ÊÓ

Consider graphs with \(n\) vertices. Remember, graphs do not need to be connected. (a) How many edges must the graph have to guarantee at least one vertex has degree two or more? Prove your answer. (b) How many edges must the graph have to guarantee all vertices have degree two or more? Prove your answer.

Suppose \(G\) is a connected graph with \(n>1\) vertices and \(n-1\) edges. Prove that \(G\) has a vertex of degree 1 .

Prove that \(K_{3,4}\) is not planar. Do this using Euler's formula, not just by appealing to the fact that \(K_{3,3}\) is not planar.