Graph Theory Practice Exam

Graph Theory Practice Exam.

1. A tree is a connected graph without any cycles. How many edges does a tree with n vertices have?

2. A spanning tree of a graph G is a subgraph T of G that contains all the vertices of G such that T is a tree. Prove, using induction on the number of vertices, that every graph G contains a spanning tree. (Hint: in the inductive step, consider the cases where the n+1st vertex, v, is or is not, a cut-vertex in the graph).

3. Draw K6. How many edges does its complement have?

4. Draw a 2-connected bipartite graph.

5. Draw a planar graph with 7 vertices that is a triangulation.

6. Let G be a 2-connected graph. Form graph G’ from G by adding a vertex v which is adjacent to two vertices of G. Prove that G’ is 2-connected.

7. Draw a 3-regular graph having more than 4 vertices.

8. What is the chromatic number of the following graph?

9. Is the following graph bipartite?

10. How many maximum length paths does C5 have?