### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# GRAPH THEORY MATH 4690

UGA

GPA 3.56

### View Full Document

## 91

## 0

## Popular in Course

## Popular in Mathematics (M)

This 22 page Class Notes was uploaded by Joanne Bergnaum on Saturday September 12, 2015. The Class Notes belongs to MATH 4690 at University of Georgia taught by Staff in Fall. Since its upload, it has received 91 views. For similar materials see /class/202081/math-4690-university-of-georgia in Mathematics (M) at University of Georgia.

## Reviews for GRAPH THEORY

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/12/15

MATH 4690 Azoff Spring 2008 Notes Pages Topic 1 7 2 Material Covered 3 Chapter 1 Problems 4 7 5 Chapter 2 Problems 6 7 8 Chapter 3 Problems 9 7 11 Chapter 4 Problems 12 7 14 Chapter 5 Problems 15 7 16 Chapter 6 Problems 17 Chapter 7 Problems 18 Chapter 8 Problems 19 Chapter 10 Problems 20 7 22 First Hour Test 23 Second Hour Test Material Covered Chapter 1 Textual treatment followed in class Chapter 2 Simple graphs emphasized More examples relating to graph homomor phisms given in class Chapter 3 Variation of Theorem 37 characterizations of trees highlighting analo gies to linear algebra concepts of independence and spanning presented in class Chapter 4 Section 6 on electrical networks not covered in class Chapter 5 We did some extra work on tournament graphs Section 6 in class Chapter 6 We followed the texts presentation of Sections 1 and 2 We did not cover Section 3 on blocks We covered Menger7s Theorems Section 5 before ows Section 4 and gave different treatments of these topics Here is the class treatment of Sections 5 and 4 De nitions Let u u be distinct vertices in a connected graph G 1 Two u u7paths are edge disjoint if they share no common edges 2 A vertex set S C EG disconnects u from u if every u u path must use at least one edge from S Menger s Theorem7edge version Let uu be distinct uertices in a connected graph G Write 04 for the smallest cardinality of all uu disconnecting subsets of EG and 6 for the mazrimum number of mutually edge disjoint u u7paths Then 04 B The vertex version of Menger7s Theorem was assigned for homework Both versions are easily adapted to directed graphs De nition Let f 7 0 00 For any vertex v of 3 we write fu 2 Zfe u is the initial vertex of e and f u Zfe u is the terminal vertex of e De nitions A network N is a directed graph 6 equipped with 1 two distinguished vertices s called the source and t called the sink or target and 2 a function e a 0 00 called the capacity function De nition A flow in a network is a function f a 0 oo satisfying 1 fe S ce for all directed edges e and 2 For each vertex v other than s t we have fv f v valf 2 fs 7 f s is called the value of the ow f A maximal ow is a ow whose value is greater than or equal to the value of every other ow Theorem max ow min cut Let N Ccst be a network Set 04 minZfe e E S where S C disconnects s from t and 2 the common value of all maximal flows in N Then 04 5 Note It suf ces to consider disconnecting sets of edges arising in the following way Start with a set A of vertices which includes s but not t called a source vertex cut in the text and then take S 2 e E EG the initial vertex of e lies in A while its terminal vertex lies outside of A Chapter 7 The main surface we considered is the plane We followed the text for Sections 2 and 3 A few results from Section 4 were mentioned but no proofs were given Sections 5 9 were not discussed Chapter 8 We covered everything except Theorem 89 from Section 1 and through Note 813 in Section 2 From Section 3 we proved Theorem 819 discussed the two examples following it and mentioned Brook7s Theorem 822 From Section 4 we proved the Five Color Theorem 828 you can become rich and famous by giving a short proof of the Four Color Theorem 829 We did not discuss Sections 5 or 6 Chapter 10 We proved Hall7s Marriage Theorem 1033 using the following language In the marriage interpretation we think of X as a set of girls Y as a set of boys and R C X gtlt Y as the set of compatible pairs The matching f we seek pairs each girl with a unique compatible boy so that no two girls are paired with the same boy It is not however necessary that each boy will be used in fact that will happen if and only if Theorem Suppose R C X gtlt Y is a relation For each subset S ofX set RS 2 y E Y gay 6 R for some it E S Then the following are equivalent 1 There is an injective function f X a Y whose graph is contained in R 2 For each subset S of X we have lRSl 2 Note The bipartite graph associated with R has vertex set X U Y with an edge joining it E X to y E Y if and only if the ordered pair ac y belongs to R Chapter 1 Problems 24 Give an example of a relation on graphs other than is a subgraph of that is a partial order Solution Let g be a set of graphs a The easiest partial order on g is equality that is given G VEi1 and G VEi in 9 we de ne G j G if and only ifV VE E and 11 W It is easy to check that equality is re exive antisymmetric and transitive in any setting b The other natural choice is the supergraph relation that is we define G j G iff and only if G 2 G This is a special case of the general result that the inverse relation associated to any partial order is again a partial order Note that the relation of Part a is the intersection of the two partial orders Q and 2 More generally the intersection of any family of partial orders on a set is again a partial order on that set 26 For n 2 3 let Cn be the collection of digraphs of u1u2 un that satisfy the two conditions a The underlying graph of each digraph in Cn is the cycle G7 b No digraph in Cn is a directed cycle What is the cardinality of Cn Solution Each edge of the underlying graph 0 can be oriented in two ways Since these choices can be made independently there are 2 digraphs satisfying a Pre cisely two of these graphs are directed cycles the clockwise and counterclock wise77 orientations so the answer to the question is 2 7 2 B34 Can we associate a partially ordered set to any finite simple acyclic digraph V E 7 Solution We use the language of Chapter 2 which is probably where this problem belongs Define a relation 5 on V by declaring u j u if and only if there is a directed path starting at u and ending at u The fact that single vertices are considered directed paths shows that j is re exive Antisymmetry follows from the acyclic hypothesis Transitivity is established by composing the two directed paths involved Chapter 2 Problems 7 not graded Suppose G and G are two simple graphs having n vertices For what values of n is it possible for G to simultaneously have more components and edges than G 7 Solution The answer is n 2 5 First consider cases to show the condition cannot hold for n 4 It follows that the condition cannot hold for any n lt 4 because if it did we could get an n 4 example by adding n 7 4 isolated vertices To get an example for n 5 take G to be a path of length 4 1 component and 4 edges and G to be the union of K4 with an additional isolated vertex 2 components and 6 edges Examples for higher n can be constructed by adding additional isolated vertices to this G G 13 not graded Which of the graphs in Figure 225 are isomorphic 7 Solution Call the graphs G1G2G3 They are all isomorphic For the shortest writeup appropriately label the vertices of G1 as u1u8 and those in G2 as 111 u8 Then define f1 by f1uj obj l n You should then check by exhaustion or inspection that uh uj is an edge of G1 if and only if 15 1 is an edge of G2 Because these are simple graphs f2 is completely determined by f1 and you don7t really have to write it out separately The isomorphism of G1 G3 is handled similarly B23 Let G be a simple graph on n vertices which is isomorphic to its own complement G For some integer k we must have n 4k or n 4k 1 Proof If G is to be isomorphic to its complement it must have exactly half as many edges as the complete graph K7 that is G must have 1671 edges The latter number must therefore be an integer and that happens iff n leaves a remainder of 0 or 1 when divided by 4 When n 4 there is only one possibility for G up to isomorphism namely the bipartite graph K272 For n 5 there are three non isomorphic possibilities for G 24 Let G be a simple graph on n vertices Then either G or its complement G is connected Proof Suppose G is not connected Then G has at least two components Let u u be distinct vertices If they lie in different components of G then they are in fact adjacent in G On the other hand if uu lie in the same component of G there is a vertex in lying in a different component of G and mm provides the desired it u path in G 30b For n gt 1 the bipartite graph K7 is not a contraction of Kn17n1 Proof When we put two or more connected vertices of Kn17n1 in a common equivalence class that class will be adjacent to every other equivalence class in the contracted graph However no vertex of K7 is adjacent to all other vertices in Km B33 Let G be a simple graph on n vertices a Every contraction of G is isomorphic to a homomorphic image of G b C v Subgraphs of G need not be isomorphic to homomorphic images of G v Minors of G need not be isomorphic to homomorphic images of G Proof For a just map each vertex of G to its equivalence class in the partition de ning the contraction For b take G K2 and form G by deleting the edges of G Since G is disconnected it cannot be the homomorphic image of the connected graph G Since subgraphs are in particular minors the same example works for 34 not graded For each natural number N define 9N KmmzmgnandmnN Then no member of g is isomorphic to a minor of another member of 97 Proof Fix N All members of 9N have N vertices Thus all minors involved in such an isomorphism must also have N vertices This precludes the presence of a non trivial contraction in the formation and we just need to show that no subgraph of one of the members 9N can be isomorphic to one of its other members So suppose m1 lt m2 and take 71 N 7 mi Then Km 1 has fewer edges than men The same is true for all subgraphs of Km1ri1 and thus none of them can be isomorphic to men On the other hand some of the vertices of Km1 111 have degree 711 but the degree of each vertex of any subgraph of Km is at most 112 Thus no subgraph of me2 can be isomorphic to Kmhm 27712 This does not contradict the Minor Theorem 240 because each 9N is a finite set B40 Consider a boxing tournament involving 11 boxers where all pairs fight each other and no ties are allowed How many outcomes are possible if every boxer wins at least one match and loses at least one match Solution Write X for set of all possible outcomes of an n boxer tournament with no ties Since there are individual matches the cardinality of X is given by lX in rm We next count the set A of outcomes where some boxer wins all his matches first decide which boxer it will be 11 choices and then decide how n71gtltn72gt f the matches not involving this particular boxer will turn out 2 Thus lAl n2ltn71gt2ltn72gt The set B of tournaments in which some player loses all his matches has the same cardinality Finally we count the intersection A B first pick an overall winner 11 choices then an overall loser n 7 1 choices then n72gtltn73gt 2 choces By the cho ces the results of all matches not involving these fighters 2 inclusion exclusion principle the answer to the problem is W WU nil2r2 le7lAl7lBllA Bl2 2 72n2 moms 2 nn 712 When n 3 this yields precisely two outcomes Labeling the players as a b c these correspond to the two ordered cycles a beats b beats c beats a and a beats c beats b beats a Thus in a round robin tournament involving three players without a big winner or a big loser there is always a three cycle involving the players Chapter 3 Problems B4 State necessary and suf cient conditions on an ordered n tuple of positive integers d1 3 d2 lt 3 1 in order that there be a tree T on n vertices so that these numbers are the degrees of the trees vertices Solution We assume n gt 1 Since any tree on n vertices must have n 7 l edges an obvious necessary condition is that 2d 2n71 To establish suf ciency we need to start with an arbitrary sequence satisfying and construct a tree on n vertices having that as its degree sequence For n 2 we have d1 d2 l and the corresponding tree has a single edge incident to its vertices We take this as our base case and complete the argument by induction on 11 So suppose that n gt 2 that we already know how to construct the desired trees on n 7 1 vertices and that we are given d1 3 3 d7 satisfying Note that implies d1 d2 l but 1 gt 1 Write j for the smallest subscript satisfying 1 gt 1 Construct a new degree sequence by lopping off d1 and reducing d by 1 Apply the inductive hypothesis to get a tree T corresponding to this new sequence We then get the desired tree T corresponding to the original sequence by adding a new leaf to T which is incident to a vertex of T having degree d 7 l 7 Let A S 3 Show that for infinitely many values of 11 there is a tree T having n vertices exactly T ll of which have degree A Proof Suppose n is congruent to 2 modulo A 7 1 that is n 2 jA 7 l for n some j E N Note that j so the proof will be complete when we build a tree T having n vertices of which exactly j have degree A To construct T start with a path 1 having j vertices Then add A 7 2 leaves at each internal vertex of and A 7 1 leaves at each endvertex ofp The resulting tree has j j 7 2A 7 2 2A 71 jA 7 l 2 n vertices in all By construction each vertex of 1 has degree A in T that is T has exactly j vertices of degree A B8 For A 2 3 consider all trees where each vertex has degree A of less and where the longest path is of length k or less Show that the maximum number mw of leaves among such trees satisfies by S AA 7 l 1 Proof Assume k is even and that T is a tree satisfying the given conditions having the largest possible number of leaves Choose a longest path 1 in T Then 1 has length k because otherwise we could add A 7 1 new leaves to T incident to one of the ends of p We consider T as rooted at the center of p Note that all vertices of T other than leaves must have degree A since otherwise we could add more leaves to T similarly all leaves of T must occur at its highest level Thus there are A vertices on the first level of T AA 7 1 vertices on the second level etc through AA 7 l 1 vertices on the highest level of T This completes the proof since we have already observed that all leaves of T must occur on this highest level Note that the proof shows that the bound given for by is actually attained The argument for odd k is undoubtedly messier it is also less satisfying since the bound given for by is not tight in that case 12 Let k E N and consider the sequence 5 on the k2 first natural numbers given by s sksk1 8281 where 31 2 lk l i7 lk2 i7 lk Then 5 has no monotone subsequence of length k 1 Proof Let7s first look at an example Take k 3 Then the terms in 51 are 1713 l 1 followed by l 7 l3 2 2 followed by l 7 l3 3 3 In other words 51 123 Similarly 52 456 and 33 789 The full sequence 5 is formed by cancatenating 53 52 51 in that order that is s 7 8 9 4 5 6 l 2 3 The desired conclusion is that s does not have a strictly increasing subsequence of length 4 nor does it have a strictly decreasing subsequence of length 4 You can follow the proof below in this special case To prove the general statement we refer to sk as the rst block of s and sk1 as the second block of 3 etc through 51 as the k th or last block of s The two key observations are that 1 each individual block is increasing but 2 entries in later blocks are always smaller than entries in earlier blocks Now suppose we have a subsequence t of s of length k 1 By the pigeonhole principle some pair of the terms of 15 will lie in a common block of 8 By 1 the latter occurring of these terms will be larger than its earlier occurring companion and this prevents 15 from being decreasing Similarly some pair of the terms oft will lie in different blocks By 2 the latter occurring of these terms will be smaller than its earlier occurring companion and this prevents 15 from being increasing B24 Suppose you delete a center from a tree thereby separating the tree into sev eral components What can be said about the maximum size of these components Solution l interpret size as meaning number of vertices Let T be a tree on n gt 2 vertices and write X for its diameter Also write 1 for one of its centers and denote the size of the largest component of T 7 v by 0 Then 0 S n 7 l 7 and this bound is tight Proof For simplicity of notation suppose that X is even Let p be a path in T of length X and write any for its endvertices Then 1 is the unique path between at and y and it must pass through 1 Thus T 7 v has at least two components two of which must contain the halves of p 7 1 Thus each component of T 7 1 must exclude v and at least half 7 of p 7 v This establishes the desired upper bound 0 S n 7 l 7 for even X To see that this upper bound is tight start with a path of length X and add 11 7 X leaves at one of its penultimate vertices The argument for odd X is similar 26 Suppose the longest path in a tree T has even length X Then all paths of length X in T have the same midvertex Proof The easiest approach is by induction on k 2 The result is clear for k 0 Assume it holds for a given k suppose T is a tree whose largest path length is 2k l and let p 1 be two paths in T having this length Form a new tree T by removing all leaves from T and write 19 q for the paths obtained by deleting the leaves of p 1 respectively Then 2k is the largest path length in T Since 19 q are paths of this length in T the inductive hypothesis tells us that 19 1 share the same midvertex v The proof is concluded by noting that v is also the midvertex of p and q 34 Write a definition for regular binary tree equivalent to Definition 329 but expressed in terms of internal vertices Solution A non trivial binary tree is regular if its root has degree 2 and all of its other internal vertices have degree 3 39 Let 1 denote the number of binary trees on n vertices Show that b1 b2 1 and that b7 bnil b1bn2 bgbnig bn72b1fOI all n gt 2 Proof Recall that binary trees are rooted and ordered It is clear that b1 b2 1 To establish the recursive formula suppose T is a binary tree on n vertices and write 1 for its root There are two cases If v has degree one then T 7 v is a tree on n 7 1 vertices and by definition there are 1974 such trees The second case is when v has two children Each of these heads a tree of its own denoted Tl for left subtree and Tr for right subtree respectively Suppose Tl has k vertices By definition there are bk possibilites for such a tree Moreover Tr must have n 7 1 7 k vertices and again by definition there are 19744 possibilities for TT Since these choices of Tl and Tr can be made independently and these choices totally deterrnine T we see that this subcase accounts for bkbn1k possibilities that is there are bkbn1k binary trees on n vertices in which the root has two children the left one of which heads up a tree 7172 on k vertices Since 1 S k S n 7 2 we see that there are 2 bkbn1k total trees k1 in the second case Adding this to the count we found for the first case we obtain 71 2 b7 1974 717 Z bkbn1k as desired k1 B41 Let 1901 be the number of complete binary trees on 211 1 vertices of the optimal low height of Tlog2n Show that 2110g2n111 Mn glowan 7 n 1 Proof All of the trees in question have height h Tlog2n By definition of complete the levels 0 through h 7 1 of these trees must be complete so these levels must account for a total of 1 2 22 717 2h 1 2h 7 1 vertices This leaves us with 211 1 7 2h 7 1 vertices to put on level h On the other hand there are 2h positions available on this h7th level However since our trees must be full we must use these available positions in pairs That means 2h 1 available pairs of which we must choose 2n 1 7 2h 717 1 n 1 7 2h 1 for placement of those vertices not used on previous levels Alternatiely we can choose the available position pairs which will be vacant There are 2h 1 7 n 1 7 2391 1 2h 7 n 1 2h71 as desired of these This gives the answer bn 2h 1 7 n Chapter 4 Problems 3 Draw all spanning trees of the graph G shown in Figure 415 Solution G has eight spanning trees 4 Every edge incident to a leaf in a connected graph G is an edge in every spanning tree of G Proof Suppose u is a leaf of G ie dam l and write e for the unique edge incident to it Now let T be a spanning tree of G Then it must be a vertex of T and since T is a connected graph with more than one vertex it cannot be isolated Thus T must include some edge of G incident to u and that edge must be e 10 Compute 7K27n and generalize to 7K37n and 7Km7n Of course 7K271 1 We give three computations of 7K27n Let G be the simple graph on vertices u1u2u1 1 having edges between each ui and each u and no others First computation To build the general spanning tree for G we first decide which 1 will be connected to both ul and U2 There are n choices for this Once this choice is made each remaining u vertex must be joined to ul or 1L2 but not both That is two choices for each of these remaining u vertices All together this accounts for TG n2n 1 spanning trees of G This can be expressed recursively as TltK277Igt 2TltK2n1 27171 Second computation courtesy of Mr Moore Consider first those spanning trees of G in which on is only joined to ul Then the remaining edges must constitute a spanning tree of Gu1u2u1 un1 and there are 7K27n4 of these Similarly there are 7K27n4 spanning trees of G in which on is only joined to 1L2 Finally we must consider those spanning trees of G in which on is joined to both ul and Hg For these each of U1 un1 must be joined to precisely one ui and thus there are 27quot1 such trees Adding we see 7K27n 27K27 4 27quot1 as in the first computation Third computation courtesy of Ms Sheutsou Write e for the edge of G joining ul to on Applying Theorem 44 we obtain TG TG 7 e TG e As in the previous computation there are 7K27n4 spanning trees of G 7 e Write in for the contracted vertex of G e It is adjacent to all the remaining vertices u2u1un1 Also write f for the edge joining in to 1L2 A second application of Theorem 44 gives TG e TG e 7 f TG e f Once again G e 7 f has the same number of spanning trees as K2 1 On the other hand the newly contracted vertex it of G e f is doubly joined to each of the remaining vertices U1 4174 it thus has 27quot1 spanning trees Substituting and adding yields 7K27n 27K27n1 27quot1 as before M71 n71 More generally 7Km7 n m 12 Draw the tree with Prufer code 111165 Solution 111 is adjacent to 112 03 v4 v7 and v6 The two remaining edges join 06 to 05 and 05 to Ug 19 Let G be a simple graph on n vertices labeled as VG 711 ow with adjacency matrix A 2 AG Show that demi 1222 for each vertex ui What happens when every distinct pair of vertices have precisely k edges between them 7 2 Proof By the way we multiply matrices we have 122 21 oi aji By symmetry of AG and simplicity of G we always have aijaji of oi Thus the above formula simplifies to 1222 21 oi the right side of which is demi by definition The formula fails for a graph consisting of one vertex with a single loop When every distinct pair of vertices in a graph G on n vertices have precisely k edges between them then each off diagonal entry of AG is k so 1222 n 71k2 20 Let G be a graph on the n vertices labeled as VG 711 un Then for each k the ij7th entry 12 of AGk is the number of distinct walks from ui to u of length k in G Proof Argue inductively on k The base case k 1 is true by definition For the inductive step use 15 2211 oil 15 22 Let G be a graph on n gt 2 vertices labeled as VG 711 un and set Y AG 141G2 AG 1 Then G is connected iff all entries of Y are strictly positive The hypothesis H gt 2 omitted in the text is necessary Proof Suppose first that all entries of Y are strictly positive and let aim be distinct vertices in VG Then the ijth entry of some power of AG is non zero so the preceding problem yields a lo1 walk which means G is connected Conversely suppose G is connected and fix 1 S i lt j S 11 There are many walks between ui and uj but at least one of these is a path and thus must have length 1 S k lt n This means yij gt 12 gt 0 Even when i j there is a walk of length two starting and ending at ui so yij 2 12 gt 0 25 Let G be a loopless graph on n vertices with k components Then rankB1G n 7 k Proof We did the case k 1 ie G connected in class Alternatively you can quote Theorem 421 and the third bulleted item on Page 110 from the text for this case For the inductive step assume the result for graphs with k 7 1 components and suppose G is a loopless graph on n vertices with k components Fix a component G of G and write H for the union of the remaining components of G Write X for the number of vertices of G Label the vertices of G by starting with the vertices of G and then appending the vertices of H Do the same for the edges of G Then the directed incidence matrix of G takes the block form 340 0 0 371H The inductive hypothesis tells us rank 310 X 7 1 and rank 31H n 7 X 7 k 7 1 Adding we obtain rank 31G n 7 k as desired 30 Use the matrix tree formula to compute 7K27n for each n 2 2 Proof Label the vertices as in Problem 10 above The 11 cofactor of the resulting matrixis n 71 71 71 2 We evaluate this determinant by adding half of each of columns 2 through n to the first column That yields an upper triangular matrix whose first diagonal entry is g and whose other diagonal entries are all 2 Thus 7K27n 2 1127171 B32 Use the matrix tree formula to compute 7Km7 for all m n E N Proof Computations like those of Problem 30 yield 7Km7 nm lmn l 34 Let W7 be the wheel on n 1 vertices Compute 7W3 and TW4 Solution W3 is isomorphic to K4 so 7W3 44 2 16 by Cayley7s Theorem 3 71 0 71 3 71 0 The matrix tree theorem yields TW4 det 0 71 3 71 45 71 0 71 3 The general formula for 7W is given in terms of the Lucas numbers The latter are defined recursively by L1 1L2 3 and L7 L71 L72 for n gt 2 Then 7W L27 7 2 38 Suppose the weighted graph G W has a unique edge em of minimal weight Then em is part of every minimal cost spanning tree of G Proof Suppose T is a spanning tree of G which excludes em Adding em to T creates a single cycle 0 We can get a new tree T by removing an edge other than em from 0 Then T is still a spanning tree for G but its total cost is less than the cost of T This prevents T from being a minimal cost spanning tree for G Note This problem is not about a specific algorithm but it can be extended to show that if the weights of G W are distinct then G has a unique minimal cost spanning tree In this case Kruskal and Prim must construct the same minimal cost spanning tree though they may choose its edges in different orders 41 Draw a connected weighted graph for which Kruskal7s and Prim7s algorithms can find different minimal cost spanning trees Solution The simplest example is a graph on two vertices having two edges with equal weights incident to them As mentioned in class a triangle with equally weighted edges will also work B11 Let u be a fixed edge of the complete graph K7 and write Tun for the number of spanning trees of K7 that include u as a leaf Compute limnnoo Tu n TKn39 Proof Suppose T is a spanning true of K7 containing u as a leaf Then u must be joined to another vertex n 7 1 choices and T 7 u must be a spanning tree of K71 Thus Tun n 7 ln 7 l 3 n 7 D7quot2 and limnnoo 32 l e nmw 7171 Chapter 5 Problems 1 For what values of n are the graphs Nn P7 K7 bipartite 7 Solution Our text allows the partition sets appearing in the de nitions of bipartite and k partite graphs to be empty We discussed the pros and cons of this in class l7ll go with the book primarily because otherwise Problem 4 would be false This means N7 is bipartite for every n E N and in particular so are P1 K1 N1 In fact P7 is bipartite for every 11 If the underlying vertices are labeled 1L1 un we take X ujjj is odd and Y ujjj is even In particular K2 P2 is bipartite K7 is not bipartite for any n 2 3 Indeed suppose XY are disjoint subsets of VKn with and Kan null and for definiteness that U1 6 X Then 1L2 cannot belong to X so we assume it belongs to Y But that means 1L3 which is adjacent to both m m cannot belong to X or Y This proves that X U Y cannot exhaust VKn whence K7 is not bipartite 4 Show directly from the definition that every subgraph of a bipartite graph is also bipartite Proof Suppose G is a subgraph of the bipartite graph G Choose XY as in Definition 51 that is VG is the disjoint union of X and Y with GjX and GjY having empty edge sets Then de ne X VG X and Y VG Y Complete the proof by checking that X U Y VG but X Y Q and that GXj and GYj are null graphs 8 Determine which graphs in Figure 513 are Eulerian and which have Eulerian trails Solution Note that every circuit is also a trail and thus every Eulerian graph has an Eulerian trail Thus Corollary 58 is misstated It should read A connected graph G has an Eulerian trail if and only if all except at most two vertices in G have an even degree The leftmost graph in Figure 513 has four vertices of odd degree and hence does not even admit an Eulerian trail The middle graph has two vertices of odd degree and hence admits an Eulerian trail but not an Eulerian circuit The rightmost graph has no vertices of odd degree and hence admits both Eulerian trails and Eulerian circuits 14 Neither of the graphs illustrated in Figure 56 is Hamiltonian Solution Deleting the six middle vertices from the top graph creates seven com poncents which removing the middle four vertices from the bottom graph creates five components Theorem 516 therefore tells us that neither graph is Hamiltonian 15 For each n 2 2 the bipartitie graph K7 is Hamiltonian Proof Note Theorem 516 is of no help in this problem since its converse is not valid For a correct proof you can either construct the desired Hamiltonian cycle directly U101u202 unv ul or apply Corollary 521 18 For which m n is the grid graph gtlt Hamiltonian 7 Solution Clearly l gtlt is Hamiltonian iff n 1 so we restrict attemtion to the non trivial case where m and n are both greater than one Then a Hamiltonian cycle exists iff mm is even Su iciency is established by constructing a snakelike cycle when either m or n is even There are several different approaches to establish necessity 1 Every cycle in a grid graph must include as many right moves as left moves and as many up moves as down moves Thus every cycle in a grid graph has even length and hence includes an even number of vertices 2 Ms Donaldson and Ms Hallman Every grid graph is bipartite whence all cycles have even length by Theorem 53 Mr Gold Suppose mn are odd and take S ij E gtlt ij is odd Then 5 quotW271 while gtlt 7 S is a null graph having M components Thus Theorem 516 tells us that gtlt cannot be Hamiltonian A co V 26 Equip the edges of the complete graph K7 with strictly positive weights and let 0 a minimal cost Hamiltonian cycle in K7 and T a minimal cost spanning tree in Kn Then W0 gt Proof Let 6 be any edge of 0 Then 0 7 e is a spanning tree so W0 gt W0 7 e 2 Note It is not always possible to choose 6 so that 0 7 e is itself a minimal cost spanning tree Consider for example K4 W3 with all outer edges having weight 2 and all spokes having weight 1 Here W0 6 removing an edge from 0 leaves paths of cost 4 or 5 but the minimal cost spanning tree consists of the spokes and has cost 3 31a Let 0 be a weakly connected digraph Then 0 has a directed Eulerian circuit iff all vertices of 0 have equal in and out degrees Proof Suppose first that 0 has a directed Eulerian circuit 0 Then 0 must enter each vertex the same number of times it leaves it Conversely suppose du d for each u E Start a circuit 0 at some vertex u of It can only end at u If 0 doesn7t use up all edges of 0 add in side trips as we did in the undirected case 31b Let 0 be a weakly connected digraph which is not Eulerian Then the following are equivalent 1 0 has an Eulerian trail 2 0 has precisely two vertices with unequal inout degrees One of these must satisfy du d l and the other must satisfy dv d v 7 1 Proof This can be proved the same way as Part a noting that if a trail starts at u and ends at v 31 u then you will leave it once more than you enter it and you will enter 1 once more than you leave it Alternatively you can apply the result of Part a by adding a single directed edge to the graphs appearing in this part 32 Suppose the directed graph G has a directed Eulerian trail but does not have a directed Eulerian circuit Prove that the underlying graph G does not have an undirected circuit Proof Choose u as in Problem 31b Then du du d 2d l is odd so an undirected Eulerian circuit is ruled out by Theorem 57 40 For n 2 3 there are 2 7 2 acyclic directed graphs having the cycle 0 as underlying graph Solution Each edge of the underlying graph 0 can be oriented in two ways Since these choices can be made independently there are 2 digraphs with underlying graph G7 Precisely two of these graphs are directed cycles the clockwise and counterclockwise orientations leaving 2 7 2 acyclic directed graphs 43 If a digraph G contains a directed circuit of positive length then G must contain a cycle 7 Proof Let G be a circuit in G of minimal length and note that this must be a cycle Mr Conway and Mr Posey noted that the present result also follows from Corollary 545 45 The following are equivalent for a digraph G on n vertices l G is acyclic 2 There is a labeling of the vertices relative to which the adjacency matrix is strictly lower triangular Proof Follow the proof of Corollary 546 or use its result by noting that reversing the order of the vertices 1L1 u results in a transposed adjacency matrix B6 Let G be a k partite graph on n vertices Then G is kaartite for every k S k S 11 Proof lt suf ces to consider the case k k 1 Handle this by splitting one of the sets in the original partition into two subsets The convention of allowing empty parts makes this problem trivial B16 Suppose n 2 m gt 1 Then the complete bipartite graph Km is Hamiltonian if and only if m 11 Proof Problem 15 above shows the condition is suf cient For necessity note that any cycle in a bipartite graph must use the same number of vertices from each part Alternatively you can delete the part S consisting of the m vertices noting that Km 7 S is then a null graph having 11 components and Theorem 516 applies Chapter 6 Problems 1 Let U be a cut veriex of a simple graph Then 1 is not a cut vertex of the complementary graph G Proof Let G be the component of v in G and suppose ac y are distinct vertices in G 7 1 We must show that there is an ac y path in G 7 1 We first consider the case when gay belong to different components of G 7 1 Then in particular ac y are not adjacent in G and hence they must be adjacent in G Thus any provides the desired path of length one in G 7 1 Suppose now that we are in the opposite case that gay belong to the same component of G 7 v This is where we use the hypothesis that v is cut vertex of G to obtain a vertex 2 in a different component of G 7 v This means at and y are both adjacent to z in G and hence aczy provides the desired ac y path of length 2 in G 7 v 3 Let c be a bridge of a graph G having k components Then G 7 c has k 1 components Proof It is not legitimate to assume the result of this problem for connected graphs nor is it proper to assume that G itself is connected Let G be the component of e in G Since removal of 6 does not affect any of the other components of G it suf ces to show that G 7 c has exactly two components We know G 7 c has at least two components because otherwise G 7 6 would have the same number of components at G Write gay for the endvertices of e and suppose v is a vertex in G Because G is connected there is a path 1 from v to ac If this path does not include the edge c then 1 lies in the same component of G 7 e as ac In the contrary case that e is included in p then 1 v yeac and we see that 1 lies in the same component of G 7 e as y Thus G 7 c has at most two components and the proof is complete 12 Let u be a vertex in a graph G Then the following are equivalent 1 u is a cut vertex for G 2 There are vertices 11111 not equal to u in the same component of G as a such that every path between 1 and w contains a Proof Write G for the component of G containing a Assuming l we get 2 by choosing v w in opposite components of G 7 a For the reverse implication note that 2 implies vw cannot lie in the same component of G 7 a Note The italicised words were omitted in the texts statement of the problem But then 2 would be vacuously satisfied for any choice of 0111 31 u in different components of G and thus would not imply 29 Give an example of a network G with a unique maximum ow f Construction The simplest example has only two vertices together with a directed edge from the source to the sink 30 Give an example of a network G with more than one maximum ow Explain why every such network must have in nitely many maximum ows Construction Take stvw with directed edges svvwwt and mt with all four edges having capacity 1 One maximum ow is given by f1sv f1vt 1 and f1vw f1wt 0 another is given by f2sv f2vw f2wt 1 and f2vt 0 For the second statement suppose f1 f2 are distinct maximum ows for a net work Then for every real number 04 E 0 1 the convex combination afl 17af2 provides a maximum ow for that network and the functions given by these com binations are all different A Prove the vertex version of Menger7s Theorem The maximum number 04 of vertex disjoint paths connecting two distinct non adjacent vertices u v in a graph G is equal to the minimum number S of vertices which need to be removed from VGu vin order to destroy all u v paths Proof For short we refer to any set S C VGv v of minimal cardinality whose removal destroys all u 1 paths as a minimal separating set We at least have 04 3 since removing fewer than 04 vertices from VGu U will leave at least one u v path in tact For the opposite inequality we argue inductively on the cardinality of VG clearly Oz 1 when jVGj 3 For the inductive step assume the result for all graphs with fewer than n vertices and suppose that G has n vertices Every vertex in other than u v is part of some minimal separating set since otherwise we could apply the inductive hypothesis to G 7 w Similarly if there were a u v path of length two we could delete its middle vertex that would reduce both 04 and S by one and the inductive hypothesis would again kick in Applying these reductions we fix a minimal separating set S 2 1111 w3 which includes a vertex which is neither adjacent to it nor to 1 Now consider the graph G1 obtained by contracting the component of u in G 7 S to a single point 71 This graph has fewer vertices than G and still admits S as a minimal separating set Thus the inductive hypothesis provides us with W vertex disjoint 711 paths These paths necessarily take the form ftpjj 1 where p is a path in G which starts at w and ends at 1 Similarly contracting the component of v in G 7 S provides us with paths ql 13 with q starting at u and ending at 111 The cancatenated paths ql gtk p1 3 gtk p13 are vertex disjoint paths from u to v and we have 04 2 S as desired Chapter 7 Problems 3 The 6 verteX l2 edge graph described in planar Proof The simplest procedure is to redraw the graph in the form of a central triangle surounded by three congruent tangent triangles whose outlying vertices are joined with three circular arcs Alternatively one can note that neither K5 nor K373 is a minor of the given graph 4 Prove Euler7s formula inductively by using contraction of an edge in the graph Proof For the inductive step contract an edge which borders the unbounded re gion If the other side of the edge is not a 3 cycle then both the number of vertices and the number of vertices are reduced by one but the number of faces is not affected On the other hand if the bounded side of the contracted edge is a 3 cycle then one vertex two edges and one face are destroyed In either case the truth of Euler7s formula in the contracted graph implies its validity in the original graph 7 There is a planar graph all of whose vertices have degree 5 Construction The smallest example is the icosahedral graph drawn in class and pictured on the website httpbbssachinapkueducnStatMath7Worldmathii008htm B12 For each 3 S r S 5 there is an infinite collection of simple planar connected r regular graphs no two of which are isomorphic Construction The parallel sum of two planar graphs is formed by deleting one outer edge that is an edge bordering the infinite face from each and then adding two new edges joining correponding vertices of the deleted edges The new graph is planar and if the original graphs were r regular then so is their parallel sum For each n E N take G7 to be the parallel sum of n copies of the icosahedral graph of Problem 7 Then G7WEN provides the desired family for r 5 Similar constructions starting with K3 and K4 solve the problem for r 3 and r 4 respectively though there are easier constructions in these latter cases Chapter 8 Problems These problems will be discussed in the reView sessions and written up afterwards if requested 8 The ladder graphs on Page 260 of the text all have chromatic number 3 17 Suppose G1 and G2 are simple subgraphs of a given graph Then xG1 Gg S XltG1 39 XltG2 23 Let A be the adjacency matrix of a simple bipartite graph Then for each odd k all diagonal entries of A are zero The converse holds as well 31 For which k E N and a1 ak is the k partite graph Kahwak planar 7 Chapter 10 Problems Hall7s Theorem B Consider a group X of three girls 1 b c and a group Y of four boys d e f g of which the following seven pairs are compatible 16 mf 19 bad bfa0da06 a Draw the corresponding bipartite graph b Find five different solutions of the corresponding marriage problem c Check that the condition given in Hall7s Theorem is satisfied This is left to the reader For Part c you must check that lRSl 2 lSl for each non empty subset of X There are seven such sets S C A building contractor advertises for a bricklayer a carpenter a plumber and a toolmaker and receives five applicants 7 1 for the job of bricklayer 2 for carpenter 3 for bricklayer and plumber and 45 for plumber and toolmaker Use Hall7s Theorem to decide whether all of the jobs can be filled with qualified applicants Solution Take X bcpt and Y l2345 It is easy but tedious to check that Hall7s condition is satisfied One matching is provided by b 1 0 2 193 ta4 31 Let G be a bipartite graph with bipartition VG X U Y and suppose there is an integer k such that dgac 2 k 2 dgy for all x E X and y E Y Then there is a matching which covers all of X Proof Fix a non empty subset S of X As usual set RS 2 y E Y y is incident to some it E S Write A for the set of edges in G incident to vertices in S and B for the set of edges in G incident to vertices in RS The hypothesis gives lAl 2 lel and klRSl 2 Since A A B C B we get klRSl 2 3 2 lA Bl lAl 2 Dividing by k shows Hall7s condition is satisfied 34 Let X be a set of sultans and let Y be the set of potential wives Find necessary and su icient conditions that each sultan can marry k women he likes To be discussed at review session MATH CSCI 46906690 Azos a y v7 FTduke I l Solutions to First Hour Exam 100 points 7 i 3 w 1 Consider the graph G pictured in Figure 1 Equip the collection 9 of subgraphs of G with the partial order g Include brief justi cations to your answers to Parts b through e of this problem a Formally de ne this graph as an ordered triple Solution G VEw where the set of vertices is V 2 v1v2v3v4 the set of edges is E 2 e1e2e3e4e5 and the edgemap w is given by ibel v1v2we2 U2 3 111713 and W64 1Mes 03714 b Does G have a largest loopless subgraph Solution Yes It is G e2 0 Does G have a largest simple subgraph Solution No G e4 and G e5 are both maximal but neither is largest because neither is contained in the other d Does G have a maximal simple subgraph Solution Yes G e4 and G 65 both work e How many distinct isomorphisms are there from G onto itself Solution There are two Besides the identity automorphism it is also possible to interchange e4 with e5 That is all you needed to say to get full credit Feel free to skip the following technical details Formally an isomorphism from G to itself also called an auto morphism of G consists of a pair of bijections f1 V gt V and f2 E gt E which are consistent with the edgemap 2 in the sense that for any e E E the endvertices off2e can be obtained by ap plying f1 to the endvertices of e In the identity automorphism both f1 and f2 are identity maps In the flip automorphism fl is still the identity map while f2 sends eLe2e3 to themselves but interchanges e4 and e5 It is easy to check that these choices for f1 f2 are in fact consistent with the edgemap w and hence provide automorphisms of G For completeness we should also explain why these two pairs are the only automorphisms of G So suppose f1f2 is any automorphism of G We rst note that f2 must send 82 to itself because that is the only loop in the graph Thus f1 must send v2 to itself since v2 is the only vertex incident to that loop Because f1 must preserve degrees it must also send the lone vertezv 113 of degree 5 to itself It now follows that f1 sends v1 to itself because that is the only vertex simultaneously adjacent to both v2 and v3 Because fl is a bijection we have accumulated enough information to conclude that it is the identity map Consistency with the edgemap now forces f2e1 2 el and f2 3 63 This only leaves open the two possibilities of the preceding paragraph either f2 e4 2 e4 in which case we are dealing with the identity automorphism or f2 interchanges e4 with 65 2 Suppose 01 and G2 are connected sugraphs of a xed K a Prove that if 01 and G2 share a common vertex then the union 01 U G2 is also connected Solution Write w for a common vertex of 01 and G39g and suppose uv are any vertices in G1 U 02 Connectedness 0f 01 provides a u wwalh p1 while connectedness of 02 provides a w v walk p2 The composite walk p1 192 provides the needed uvwalk which can be shortened to a u v path if desired b Brie y discuss the converse of Part a Solution The converse states that ifGl UG2 is connected then G1 and G2 must share a common vertex This is true Formal proof was not required and it would have been good enough to observe that any path joining a vertex of 01 to a vertex of G2 must pass through a common vertex of the two graphs 3 Give examples of the following No justi cation is required in this problem a a simple 3regular graph on six vertices b a simple graph on vertices having 3 components and 6 edges c a simple graph which has a cut edge but does not have a cut vertex 1 a simple directed graph which is weakly connected but not strongly con nected Solution See Figures 234 and 5 respectively 1 V O 7 quotquot 39 m 39 g n a w quot Lani fr 39 I i 5 Uif elill LBWVb 3 L jigi r F bL 4 Up to isomorphism there are two distinct connected simple graphs on 3 vertices and six distinct connected simple graphs on 4 vertices a Draw the graphs on three vertices Solution See Figures 6 and 7 04 A quotT quot quot39 T w v quotquotquot 3 F 4 are 0 l i more 7 r n i mew 1 MM w b b Draw the graphs on four vertices Hint add a vertex and various edges to the graphs you found in Part a Solution See Figures 8 through 18 WM Hi Z 1 B E c Explain why no two of the graphs of Part b are isomorphic to each other Solution Figures 8 and 9 both have three edges Figures 10 and 11 both have four edges Figure 12 has ve deges and Figure 13 has six edges Since isomorphic graphs must have the same number of edges it only remains to distinguish between Figures 8 and 9 and between Figures 10 and 11 Well Figures 9 and 10 include vertices of degree three but Figures 8 and 11 do not 5 Write G for the simple graph on the vertices w1w2w3w4w5w6w7 which has 5 edges with deg wl 5 and 1127 being isolated a Draw G Solution See Figure 14 b Explain why G is not isomorphic to any subgraph of the complete bi partite graph K474 Solution All vertices ofK44 have degree four Thus none of its subgraphs can have a vertex of degree ve as G does c Explain why G is not isomorphic to any contraction of K4y4 Solution All contractions of the connected graph K44 are connected but G is not d Show that G is isomorphic to a minor of K44 Solution A minor is a contraction of a subgraph Remove edges from K414 to get the graph H shown in Figure 15 This is a subgraph of K4a4 Then contract H along the edge v1v5 to get the graph J shown in Figure 16 This is isomorphic to G 1 V1 V 1 3 V 39 V V397V V s w Wquot quotT J L 6 1 v i I 7277 1 m i 39 v v 6 1L K

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.