# Graphing with Vertices

Not what you're looking for?

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.

##### Purchase this Solution

##### Solution Summary

Questions pertaining to graphing with verticesare answered in detail.

##### 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 ...

###### Education

- BEng, Allahabad University, India
- MSc , Pune University, India
- PhD (IP), Pune University, India

###### Recent Feedback

- " In question 2, you incorrectly add in the $3.00 dividend that was just paid to determine the value of the stock price using the dividend discount model. In question 4 response, it should have also been recognized that dividend discount models are not useful if any of the parameters used in the model are inaccurate. "
- "feedback: fail to recognize the operating cash flow will not begin until the end of year 3."
- "Answer was correct"
- "Great thanks"
- "Perfect solution..thank you"

##### Purchase this Solution

##### Free BrainMass Quizzes

##### Know Your Linear Equations

Each question is a choice-summary multiple choice question that will present you with a linear equation and then make 4 statements about that equation. You must determine which of the 4 statements are true (if any) in regards to the equation.

##### Geometry - Real Life Application Problems

Understanding of how geometry applies to in real-world contexts

##### Probability Quiz

Some questions on probability

##### Multiplying Complex Numbers

This is a short quiz to check your understanding of multiplication of complex numbers in rectangular form.

##### Solving quadratic inequalities

This quiz test you on how well you are familiar with solving quadratic inequalities.