Explore BrainMass

Graphing with Vertices

This content was STOLEN from BrainMass.com - View the original, and get the already-completed solution here!

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.

© BrainMass Inc. brainmass.com October 16, 2018, 3:52 pm ad1c9bdddf


Solution Preview

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.

Similar Posting

Trees and Graphs : Vertices and Edges

1. True or False. It is possible to obtain a graph in which the number of vertices is 9, each with degree 5.

2. How many edges are there in a tree with 14 vertices? Choose one answer.
(a) 10 (b) 13 (c) 14 (d) 15 (e) none of the above

3. If there 5 sections of Discrete Math with a total enrollment of 31 students, what is the smallest possible number of students in the section with the largest enrollment?

View Full Posting Details