Graph theory homework

Prove that the Petersen graph is not planar without using Kuratowski's Theorem. [Hint: use an argument involving its girth. 15S2. Show that the Petersen graph is a minor of the graph from Homework 7B. 15S3.

This homework is optional. If you are happy with your homework grade this semester, you do not need to turn in this assignment, and this assignment will not be counted as your dropped homework. However, the material covered in this homework is on the third exam, so it may be in your best interest to work hard on this assignment.

(Remember a vertex cover is a set of vertices that is adjacent to every edge in the graph.) Given a bipartite graph Gwith bipartition V=Xunion Y, set up a network like we did in class: create a super-source sthat is adjacent toall vertices in X; then create a super-sink tthat is adjacent fromall vertices in Y.

For each of the graphs in your table of statistics, find its crossing number, thickness, genus, incidence matrix, adjacency matrix, eigenvalues, etc. . 15S5. Let Gbe a directed graph witha directed cycle.