1)Prove that every simple not directed graph with 21 vertices and 208 edges has
a hamiltonian circuit but not an Euler circuit.

(I have proved that if we give the 2 edges for each vertices then after a few
steps I have 21 vertices of odd degree and 19 edges.So in the end I have 2
vertices of odd degree.So I have not an Euler circuit.But how can I prove that
there is a Hamiltonian one?)

2)If G is a tree and has a virtex k degree,prove that it also has at least k
vertices degree 1.

I think induction...

Thank you.

Hi,

Well you're not quite looking at #1 correctly. If G was complete it would have 21C2 = 210 edges so it is almost complete - it's missing 2 edges. Think of the vertices that are end points of these missing edges (it could be two disjoint edges or a path of length 2 that is missing); it's not hard to show some of these must have odd degree (almost all have degree 20).

For # 2 start at the vertex of degree k and direct all of its incident edges away from it. Now look at the endpoints of those arcs (directed edges). Either they have no other incident edges in which case they have degree one or they have other incident edges in which case arbitrarily choose one and direct it away from the initial vertex of degree k. Since G is finite the process must end with k paths directed away form the initial vertex and the ends of these paths are vertices of degree 1.

These are only sketches of proofs you need to be more formal in your presentation.

Cheers,

Penny