1.) "The following algorithm will give a lower bound on the weight of the lightest circuit in a weighted graph G that we know has at least one Hamiltonian circuit.

Suppose V(G) = {v_1, v_2, v_3, ..., v_n}

For i = 1 to n, Apply Kruskal's Alogrithm to G - {v_i} to get a minimal spanning tree of G - {v_i}. Call it T_i. Let its weight be w(T_i). Let Weight(i) = w(T_i) + sum of weights of two lightest edges incident to v_i.
Next i
Find largest value of Weight(i) for i = 1 to n. Call it Value.

Then we have that the number of lightest Hamiltonian circuit >= Value (Value is a lower bound on the weight of lightest Hamiltonian circuit).


Apply the algorithm to the graph below to find Value, which is the best (greatest) lower bound of a lightest Hamiltonian circuit.

(Description of Graph): It's a perfect pentagon, with A at the time, and then going counter-clockwise B, C, D, E at the vertices.
On edge A to B, distance is 5; B-C is 4; C-D is 7; D-E is 8; E-A is 1. Then the graph connected all vertices (therefore creating a "star" in the middle). From A-C has distance 3; A-D is 7; B-E is 9; B-D is 5; E-C is 2.

And then the second question asks: "Find a lightest Hamiltonian circuit."

I understand the other questions about Hamiltonian circuits, but thought that this was a N = NP problem which I guess confused me.


"Let D_k(G) = the number of vertices in graph G that have degree k.
Theorem: (i) D_1(G) + 2D_2(G) + 3D_3(G) + ... = 2|E(G)|

a.) Show both parts of the theorem using the following graph:

b.) Prove both parts of the theorem.

Ok, obviously you can't see the graph, but I think I can figure that part out. For the proof, how would you suggest proving this. I am thinking using induction? Not really sure how else you could prove it. (Maybe counting pricinples)?


"In a tree, the eccentricityof a vertex x, denoted e(x), is the number of edges in the longest simple path that begins at x. (Or equivalently, it is the maximum value of d(x,v) taken over all vertices v.)"

a.) "For the following two trees, T_1 and T_2, label the vertices and find the eccentricity of each vertex."

It's quite easy to describe the graphs:
T_1: 4 vertices horizontally connected by 3 edges...the 2nd vertex has 1 edge and vertex vertically from it as does the 3rd. So it looks something like this:

| |
* *
(Probably won't format correctly; description will accurately describe it, though.)

On T_2: it has 6 vertices horizontally connected by 5 edges...the 2nd vertex has another edge, vertex, edge and vertex going vertically; the same is true for the 4th; for the 5th one, its the same as the 2nd and 4th but it has one more edge and vertex, so it looks something like this:
| | |
* * *
| | |
* * *



b.) "The center of a tree is the set of vertices whose eccentricities are the smallest. Find the center of T_1 and T_2. (If the graph represents the street map of a town, then you might want to place a hospital or police station at a center vertex.)"

c.) "Given a tree T with more than one edge, let p(T) denote the tree obtained from T by erasing all the leaves of T and their incident edges. Find p(T_1) and p(T_2). (We say that p(T) is obtained from T by pruning all of T's leaves.)

d.) "If you know the eccentricities of every vertex in a tree T, what can you say about the eccentricities of the vertices of p(T)?

e.) "If T is a tree with more than one edge, prove that the center of T is the same as the center of p(T)."

f.) "Prove that every tree has a center that consists of either one or two vertices."

I already got a, that was easy. B is easy too. I'm stuck on c, d, and e. I think I can prove f.

Many thanks!