Hamiltonian proofs
Not what you're looking for?
A) Prove that if G and H are Hamiltonian graph, then G x H is Hamiltonian.
b) Prove the n-cube Qn n>=2 is Hamiltonian.
Purchase this Solution
Solution Summary
This is a set of proofs about Hamiltonian graphs.
Solution Preview
(a) Suppose V(G)={1,2,...,n}, V(H)={1,2,...,m}. The graph GxH is defined
as P=GxH, where V(P)={(i,j): i in V(G) and j in V(H)}, E(P) is the
edge set of P. ((i,j),(k,r)) is in P if and only if (j,r) is an edge of H
and (i,k) is an edge in G.
Since G and H are hamiltonian, we can assume G has cycle: 1->2->3->...->n->1,
H has cycle 1->2->3->...->m->1.
In PxH, we want to find a hamiltonian cycle.
Case 1: (n,m)=1, then the cycle is
(1,1)->(2,2)->...(k,r)->(k+1,r+1)->...->(n,m)->(1,1). For example, n=3, m=4,
we get: (1,1)->(2,2)->(3,3)->(1,4)->(2,1)->(3,2)->(1,3)->(2,4)->(3,1)->(1,2)
->(2,3)->(3,4)->(1,1)
Case 2: n=m, then the cycle is
...
Purchase this Solution
Free BrainMass Quizzes
Probability Quiz
Some questions on probability
Geometry - Real Life Application Problems
Understanding of how geometry applies to in real-world contexts
Exponential Expressions
In this quiz, you will have a chance to practice basic terminology of exponential expressions and how to evaluate them.
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.
Multiplying Complex Numbers
This is a short quiz to check your understanding of multiplication of complex numbers in rectangular form.