Report

Group 10 Project Part 3 Derrick Jasso Rodolfo Garcia Ivan Lopez M. Section 10.1 #36 36. Recall that Km,n denotes a complete bipartite graph on (m, n) vertices. a. Draw K4,2 b. Draw K1,3 c. Draw K3,4 d. How many vertices of Km,n have degree m? degree n? e. What is the total degree of Km,n? f. Find a formula in terms of m and n for the number of edges of Km,n. Explain. Solution a) K4,2 b)K1,3 Solution c)K3,4 d) If n≠m, the vertices of Km,n are divided into two groups: one of size m and the other of size n. Every vertex in the group of size m has degree n because each is connected to every vertex in the group of size n. So Km,n has n vertices of degree m. Similarly, every vertex in the group of size n has degree m since each is connected to every vertex in the group of size m. So Km,n has n vertices of degree m. Solution e) The total degree of Km,n is 2mn because Km,n has m vertices of degree n and n vertices of degree m. f) The number of edges of Km,n = mn. This is because the total degree of Km,n is 2mn, and so, by Theorem 11.1.1, Km,n has 2mn = mn edges. 2 Section 10.1 #37 Find which of the following graphs are bipartite. Redraw the bipartite graphs so that their bipartite nature is evident. Solution a.) v1 v2 v3 v4 b.)Not bipartite. No possible way to create two subsets without vertices relating to one another within the same subset. c.) v1 v2 v3 v4 v5 v6 d.) Not bipartite. No possible way to create two subsets without vertices relating to one another within the same subset. Solution Continued d.) Not bipartite. No possible way to create two subsets without vertices relating to one another within the same subset. e.) v1 v2 v3 v5 v4 f.) Not bipartite. No possible way to create two subsets without vertices relating to one another within the same subset. Summary of Main Results Definition: Let n be a positive integer. A complete graph on n vertices, denoted Kn, is a simple graph with n vertices and exactly one edge connecting each pair of distinct vertices. Definition: Let m and n be positive integers. A complete bipartite graph on (m,n) vertices, denoted Km,n, is a simple graph with distinct vertices v1, v2, … ,vm and w1, w2, … ,wn that satisfies the following properties: For all i,k = 1, 2, … ,m and for all j, l = 1, 2, … , n, 1. There is an edge from each vertex vi to each vertex wj. 2. There is no edge from any vertex vi to any other vertex vk. 3. There is no edge from any vertex wj to any other vertex wl . Leonhard Euler Euler lived from April 15, 1707 to September 18, 1783. Euler is considered one of the greatest mathematician of all time. With contributions to calculus and wrote the first paper on graph theory. Not only was he a great mathematician but, he was also renowned for his work in mechanics, fluid dynamics, optics, and astronomy.