Math 3260 Assignment 1 Due on Friday January 21 2011 at

Math 3260 Assignment 1 Due on Friday January 21 2011 at noon. Sumbit your assignment to the drop box on the fth oor of N Ross. 1. Exercise 1.15 on Page 17: If G is a simple graph with at least two vertices prove that G must contain two or more vertices of the same degree. [5] 2. The Odd graph On is the graph whose vertices are the n-subsets of f1; 2; : : : ; 2n + 1g two n-subsets (vertices) are adjacent if and only if they are disjoint. (a) Draw O1 and O2. [2] (b) Prove that O2 is isomorphic to the Petersen graph below. [4] ajihgfedcb(c) How many vertices and edges does On have? [3] 3. Let G and H be simple graphs. (a) Show that G is isomorphic to H if and only if G is isomorphic to H. [4] (b) Determine if these two graphs are isomorphic. [4] aihgfedcb1987654321
4. Exercise 1.51 on Page 30: A simple graph that is isomorphic to its complement is self-complementary. (a) Prove that if G is self-complementary then G has 4k or 4k + 1 vertices where k is an integer. [5] (b) Find all self-complementary graphs with four and ve vertices. [3] 5. Exercise 1.44 on Page 25: Let T be a tournament on n vertices. Prove that [4] X v2V (T) outdeg(v)2 = X v2V (T) indeg(v)2: 6. For integer n 2 dene the simple graph Pn with vertex set f1; 2; : : : ; ng and i is adjacent to j if and only if i + j is a prime number. (a) Draw P5 and P6. [2] (b) Determine if Pn is bipartite for all n. Justify your answer. [4] 7. Let G be a simple graph on n vertices. Show that if G is bipartite then it has at most b n2 4 c edges. [6] 8. Show that if G is a disconnected graph containing exactly two vertices of odd degrees then these two vertices must be in the same component of G. [4] 2
Attachments: