Purchase Solution

Graphing with Vertices

Not what you're looking for?

Ask Custom Question

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

Solution provided by:
  • 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.