Consider a connected graph with 14 vertices which have degrees 4, 4, 4, 4, 4, 6,

Question

Consider a connected graph with 14 vertices which have degrees 4, 4, 4, 4, 4, 6, 6, 8, 10, 12, 16, 18, 22, and 34 respectively. Answer the following along with a brief explanation based on such a graph.

a. Determine how many edges such a graph would have or state that it cannot be determined based on the given information.

b. Determine if the graph has an open Euler trail, closed Euler trail, both, neither or state that it cannot be determined based on the given information.

c. Determine if the graph has an open Hamilton trail, closed Hamilton trail, both, neither or state that it cannot be determined based on the given information.

Explanation / Answer

a)

The sum of degrees is twice as much as the number of edges in an undirected graph.

so the number of edges will be = 4 +4+4+4+4+6+6+8+10+12+16+18+22+34

                                                  = 152/2

                                                  = 76 edges

b)

According to the theorem, If a graph is connected and every vertex has even degree, then it has at least one Euler circuit (usually more).

c)

Since this is an NP-complete problem, there is no formula to decide whether the graph contains hamiltonian path or circuit.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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