91011 thank you very much Let G V G be a graph with no loop

9,10,11

thank you very much

Let G = (V, G) be a graph with no loops and parallel edges, and |V| = n greaterthanorequalto 3. Given a detailed proof that if deg(upsilon) + deg(omega) greaterthanorequalto n for each pair of vertices v and omega which are not connected by an edge, then G has a Hamiltonian cycle. Write the Kruskal\'s algorithm. Use Kruskal\'s algorithm to find a minimal spanning tree for the weighted graph in problem # 8. Find chromatic polynomials P(G, lambda) for the following graphs;

Solution

Given: Let G = (V, G) be a graph with no loops or parallel edges and n 3 vertices. If G has the property that for each pair of nonadjacent vertices u, w V, we have that deg u + deg w n then G contains a Hamiltonian cycle. Let us say G is the complete graph with n(n1)/2 edges. Let us say we connect the vertices of G in any order such as (v1, v2, … , vn) to create a Hamiltonian path, and add edge (vn, v1) to create a Hamiltonian cycle.

Let us say the statement holds true when G has k edges. Now we will prove the theorem when G has k1 edges. Further assume G be such a graph, and let vn and v1 be a pair of nonadjacent vertices in G such that: deg(vn) + deg(v1) n. Therefore, the theorem is true for k vertices.

Let G’ be the graph obtained by adding an edge between vn and v1 in G. And hence G\' has k edges. Therefore, by induction hypothesis G’ contains a Hamiltonian cycle. Let H’ be the Hamiltonian cycle in G’. Now we have to erase the edge (vn, v1) from G’ to restore G. Now, if H’ does not contain (vn, v1) . Then H’ is a Hamiltonian cycle in G, and it is proved.

But if H’ contains (vn, v1). Next let us say H’ = (v1, v2, … , vn, v1). We know delete the edge (vn, v1) from G’ to get G back.Since deg(vn) + deg(v1) n it follows from the Pigeonhole Principle that here must exist vertices v_i1 and v_i such that v_i1 is connected to vn and vi is connected to v1. Therefore G must contain the Hamiltonian cycle H = (v1, v2, … , v_i1, vn, v_n1, v_n2, … , vi , v1).

Hence, in both the cases, deg(v)+deg(w) >=n