1- Which of the following graphs are connected? --------------------------------

Question

1-

Which of the following graphs are connected?

------------------------------------------------------

Which of the following graphs have Euler circuits?

---------------------------------------------------------

3-Which of the following graphs have hamiltonian circuits?

-------------------------------------------------------

4-

What is the edge set?

-----------------------------------------------

5-

Theorem (MAT114 Website Section 5B)

How many Hamiltonian circuits are there in a complete graph with 8 vertices?

How many Hamiltonian circuits are there in a complete graph with 5 vertices?

Explanation / Answer

1. In a connected graph, there exists a path between any two vertices on the graph. A, C, and D are connected. B is not.

2. A graph contains an Euler circuit if a) it is connected, and b) it has 0 odd vertices. A and B contain Euler circuits.

3. To know if it has a Hamiltonian circuit, you pretty much just have to try to find one. A Hamiltonian circuit is a circuit that visits each vertex exactly once before returning to the starting vertex. A and D definitely have Hamiltonian circuits and C does not. I couldn't find any for B, but I'm not sure there definitely isn't one.

4. Draw a connected graph with all even vertices where P has a degree of 4. To get the edge set, list all the edges. For the graph that I drew, the edge set is {PM, MO, ON, NP, PO, OR, RQ, QP}.

5. Plug into the given formula. a) 7!/2 = 2,520 b) 4!/2 = 12

Hope this helps!

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

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