Graph Theory question !?
Q1 - Prove or disprove: There exists a simple graph with 13 vertices, 31 edges, three 1-valent vertices, and seven 4-valent vertices?
Q2- Find upper and lower bounds for the size of a maximum (largest) independent set of vertices in an n-vertex connected graph. Then draw three 8-vertex graphs, one that achieves the lower bound, one that achieves the upper bound, and one that achieves neither?
Q3- Draw a 3-regular bipartite graph that is not K3,3 ?
Q4- For each of the platonic graphs, is it possible to trace a tour of all vertices by starting at one vertex, traveling only along edges, never revisiting a vertex, and never lifting the pen off the paper? Is it possible to make the tour return to the starting vertex?
Q5- A. Draw all the 3-vertex tournaments whose vertices are u,v,x ?
B. Determine the number of 4-vertex tournaments whose vertices are u,v,x,y ?
Q6- Prove that the cycle graph Cn is not an interval graph for any n ≥ 4?
Q7- A bridge tournaments for five teams is to be scheduled so that each team plays two other teams ?
Q8- The Petersen graph ?
Q9- Hypercube graph Q3; can you generalize to Qn?