91Ó°ÊÓ

For which \(n\) does the graph \(K_{n}\) contain an Euler circuit? Explain.

For which \(m\) and \(n\) does the graph \(K_{m, n}\) contain an Euler path? An Euler circuit? Explain.

What is the smallest number of colors that can be used to color the vertices of a cube so that no two adjacent vertices are colored identically?

Is there a connected planar graph with an odd number of faces where every vertex has degree 6? Prove your answer.

For many applications of matchings, it makes sense to use bipartite graphs. You might wonder, however, whether there is a way to find matchings in graphs in general. (a) For which \(n\) does the complete graph \(K_{n}\) have a matching? (b) Prove that if a graph has a matching, then \(|V|\) is even. (c) Is the converse true? That is, do all graphs with \(|V|\) even have a matching? (d) What if we also require the matching condition? Prove or disprove: If a graph with an even number of vertices satisfies \(|N(S)| \geq|S|\) for all \(S \subseteq V\), then the graph has a matching.

What is the largest number of edges possible in a graph with 10 vertices? What is the largest number of edges possible in a bipartite graph with 10 vertices? What is the largest number of edges possible in a tree with 10 vertices?

If a graph \(G\) with \(v\) vertices and \(e\) edges is connected and has \(v

We define a forest to be a graph with no cycles. (a) Explain why this is a good name. That is, explain why a forest is a union of trees. (b) Suppose \(F\) is a forest consisting of \(m\) trees and \(v\) vertices. How many edges does \(F\) have? Explain. (c) Prove that any graph \(G\) with \(v\) vertices and \(e\) edges that satisfies \(v

For which \(n \geq 3\) is the graph \(C_{n}\) bipartite?

Give a careful proof of Corollary 4.2.2: A graph is a forest if and only if there is at most one path between any pair of vertices. Use proof by contrapositive (and not a proof by contradiction) for both directions.