Mathematics Homework Solutions
Problem
#7013

Graphing with Vertices

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.






Attached file(s):
Attachments
6-10.doc  View File

Attachment Content Summary (Note: view attachment at the above link before purchasing. Actual attachment content may vary slightly from that shown below.)

6-10.doc
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.

Give an example of a 3-regular graph with 8 vertices.

Prove: For every even n ( 4, there is a 3-regular graph with n vertices.

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.

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.





Solution Summary

Questions pertaining to graphing with verticesare answered in detail.

Solution
What is this?
By OTA - Overall OTA Rating
Departed OTA
Purchase Cost Now
$2.19 CAD (was ~$11.97)
Included in Download
  • Plain text response
  • Attached file(s):
    • grph.jpg
$2.19 Instant Download
Add to Cart
Why you can trust BrainMass.com
  • Your Information is Secure
  • Best Online Academic Help Service
  • Students find real academic Success
Related Solutions
  • Vertices in Tree - A tree has 11 vertices of degree 3, 12 vertices of degree 2, 10 vertices of degree 4 and the remaining vertices are of degree 1. How many vertices does it have?
  • Edges & Vertices of Kn and Km,n - Please see the attached file for the fully formatted problems. Find Edges & Vertices of Kn and Km,n.
  • Finding the vertices of a hyperbola. - Find the vertices of the hyperbola with the following equation: (x-3)^2/25 - (y+4)^2/4 =1 EITHER: A) (8,-4) and (-2,-4) B) (5,-4) and (1,-4) C) (3,-2) and (3,-6) D) (3 ...
  • Discrete Math - Please help me with this one! 1. Let G be an undirected graph with n vertices. If G is isomorphic to its own compliment , how many edges must G have?
  • Hyperbola : Vertices and Foci 9y^2/25 - x^2 = 1 - Find the coordinates of the vertices and the foci of the hyperbola and sketch the graph. 9y^2/25 - x^2 = 1
Browse