For each of the following, either draw a graph satisfying the given criteria or

Question

For each of the following, either draw a graph satisfying the given criteria or explain why it cannot be done. Your graphs should be simple, i.e. not having any multiple edges (more than one edge between the same pair of vertices) or self-loops (edges with both ends at the same vertex).

a. A graph with 3 connected components, 10 vertices, and 7 edges.

b. A graph with 3 connected components, 10 vertices, and 18 edges.

c. A graph with 3 connected components, 10 vertices, and 30 edges.

d. A graph with 3 connected components and 10 vertices. 9 vertices have degree 3 and 1 vertex has degree 2.

e. A graph with 5 vertices, of which 4 have degree 4 and 1 has degree 2.

Explanation / Answer

Every graph with k vertices and n edges has at least k ? n connected components.

b and c doesnt satisy this criteria so graph cannot be drawn for b and c

Suppose a graph has a finite number of edges. Then the sum of the degrees of the
vertices is twice the number of edges.

d doesnt satisfy this rule so d is not possible

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.