Graph Theory question ?
Q1 - 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.
Q2- Prove or disprove: There exists a simple gragh with 13 vertices, 31 edges, three 1-valent vertices, and seven 4-valent vertices?
Q3- Draw a 3-regular bipartite gragh that is not
Q4- For each of the platonic graghs, 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 is not an interval graph for any tournaments for five teams is to be scheduled so that each team plays two other teams.
Q7- The Petersen graph.
Q8- Hypercube graph Q3; can you generalize to Qn?