91.1 Graphs and Their RepresentationExercises1.1.1 Let G be a simple graph. Show that m ≤ (2), and determine when equalityholds.1.1.2 Let G[X,Y] be a simple bipartite graph, where [X| = r and [Y| = s.a) Show that m ≤rs.b) Deduce that m<≤n2/4c) Describe the simple bipartite graphs G for which equality holds in (b)+1.1.3 Show that:a)every path is bipartite,b) a cycle is bipartite if and only if its length is even1.1.4 Show that, for any graph G, o(G) ≤ d(G)≤ 4(G).1.1.5 For k = 0, 1, 2, characterize the k-regular graphs1.1.6a) Show that, in any group of two or more people, there are always two who haveactlythesamemberoffriendswithinthegroupb)Describeagroupoffive people,anytwoof whomhaveexactlyonefriendincommon. Can you find a group of four people with this same property?1.1.7 n-CUBEThe n-cube Qn (n ≥ 1) is the graph whose vertex set is the set of all n-tuples of Osands, wheretwon-tuples areadjacent ifthey difer in precisely one coordinate.a) Draw Qi, Q2, Q3, and Q4b)Deternnine v(Qn) and e(Qn)) Show that Qn is bipartite for all n ≥11.1.8 The boolean lattice BLn (n ≥ 1) is the graph whose vertex set is theof all subsets of [1, 2,...,n), where tw7o subsets X and Y are adjacent if theirsymmetric difference hasprecisely one element.a)Draw BLi,BL2,BLs,and BLb) Determine u(BLn) and e(BLn)c) Show that BLn is bipartite for all n ≥1.+1.1.9 Let G[X, Y] be a bipartite graph.a) Show that x d(o) = Ever d(o).b) Deduce that if G is k-regular, with k ≥ 1, then [X = [Y]1.1 Graphs and Their Representation 9 Exercises 1.1.1 Let G be a simple graph. Show that m ≤ n 2  , and determine when equality holds. 1.1.2 Let G[X,Y ] be a simple bipartite graph, where |X| = r and |Y | = s. a) Show that m ≤ rs. b) Deduce that m ≤ n2/4. c) Describe the simple bipartite graphs G for which equality holds in (b). 1.1.3 Show that: a) every path is bipartite, b) a cycle is bipartite if and only if its length is even. 1.1.4 Show that, for any graph G, δ(G) ≤ d(G) ≤ ∆(G). 1.1.5 For k = 0, 1, 2, characterize the k-regular graphs. 1.1.6 a) Show that, in any group of two or more people, there are always two who have exactly the same number of friends within the group. b) Describe a group of five people, any two of whom have exactly one friend in common. Can you find a group of four people with this same property? 1.1.7 n-Cube The n-cube Qn (n ≥ 1) is the graph whose vertex set is the set of all n-tuples of 0s and 1s, where two n-tuples are adjacent if they differ in precisely one coordinate. a) Draw Q1, Q2, Q3, and Q4. b) Determine v(Qn) and e(Qn). c) Show that Qn is bipartite for all n ≥ 1. 1.1.8 The boolean lattice BLn (n ≥ 1) is the graph whose vertex set is the set of all subsets of {1, 2,...,n}, where two subsets X and Y are adjacent if their symmetric difference has precisely one element. a) Draw BL1, BL2, BL3, and BL4. b) Determine v(BLn) and e(BLn). c) Show that BLn is bipartite for all n ≥ 1. 1.1.9 Let G[X,Y ] be a bipartite graph. a) Show that
v∈X d(v) =
v∈Y d(v). b) Deduce that if G is k-regular, with k ≥ 1, then |X| = |Y |