Please see the attached file for the fully formatted problems.

6. Suppose G is a graph and (G)  n/3. Prove that G has one or two connected components.

7. a. Prove if n is odd, then there is no 3-regular graph with n vertices.
b. Give an example of a 3-regular graph with 8 vertices.
c. Prove: For every even n  4, there is a 3-regular graph with n vertices.

8. Prove: given a graph G with 14 vertices, there is clique in G of size  3 ( (G)  3) or there is an independent set in G of size  5 ((G)  5).
Using notation from class, I'm asking you to give one half of the proof that r (3,5) = 14.
You may use the fact that r(3,4) = 9.
Hint: Consider 2 cases- either there is vertex of degree  5 or every vertex has degree  4.

9. Suppose T is a tree with n vertices, an every vertex has degree 4 or is a leaf. How many leaves does T have?

10. Find the clique number an independence number of the following graph. Prove your answers are correct.

6.) for completeness of degree (N-1), no. of vertices: N

so for (n/3) degree, there should be at least (n/3 + 1) verices. Now let these (n/3 + 1) vertice make a sub graph.
Now, rest of the (2n/3 -1) vertices:
Again for (n/3) degree at least (n/3 + 1) vertices are needed. now left no. of vertices: (n/3 -2)
and definitely to be of degree n/3 degree these number of vertices ...

Solution Summary

Questions pertaining to graphing with verticesare answered in detail.

Trees and Graphs : Vertices and Edges. 1. True or False. ... Trees and Graphs, Vertices and Edges are investigated. The solution is detailed and well presented. ...

... To see that we would create a 4-critical graph by connecting vertex 0 to vertex 3n, note that in such a graph, vertices 0 and 3n would have to be colored with ...

... emerging from vertex i of graph G. If an edge of graph G connects between vertices i and j, the respective vertex of L(G) has (n_i+n_j) edges emerging from it. ...

... Form a graph that consists of two components: the complete subgraph on s vertices, and a cycle on r vertices. Every vertex in the first component has degree s ...

... As stated in the question that if a graph has a large number of vertices and each vertex has a large degree, then the chromatic number would have to be large. ...

... 14 advanced quadratic equation questions that address lines of symmetry, graphing functions, vertices and ordered pairs. 1. Find and label the vertex and the ...

... connected graph from G, we would have to remove either all the vertices in A or all the vertices in B . Otherwise, we would still have at least one vertex v in ...

... Recall that a simple path in a graph is a path which does not have repeating vertices. To find the number of simple paths connected the vertex 1 with the ...