### Create a StudySoup account

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

Already have a StudySoup account? Login here

# MULTIDIMENSIONAL CAL MATH 2057

LSU

GPA 3.72

### View Full Document

## 10

## 0

## Popular in Course

## Popular in Mathematics (M)

This 9 page Class Notes was uploaded by Madison Gottlieb Sr. on Tuesday October 13, 2015. The Class Notes belongs to MATH 2057 at Louisiana State University taught by Staff in Fall. Since its upload, it has received 10 views. For similar materials see /class/222636/math-2057-louisiana-state-university in Mathematics (M) at Louisiana State University.

## Similar to MATH 2057 at LSU

## Popular in Mathematics (M)

## Reviews for MULTIDIMENSIONAL CAL

### 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: 10/13/15

Introduction to Graph Theory Notes for MATH 4171 RA Litherland January 127 2009 Contents C Preliminaries Graphs 0 Degree sequences CO Connectedness 4 Graphs and matrices 0 Blocks d3 Connectivity 7 Trees 0 Counting trees CD Permutation groups 10 Automorphism groups of graphs 11 Eulerian graphs 12 Hamiltonian graphs 13 Elements of plane topology 11 15 22 24 29 34 36 39 42 45 48 51 14 Planar graphs 52 15 Kuratowski7s Theorem 56 16 Crossing number 63 17 Vertex colorings 68 18 The Fourcolor Theorem 72 19 Edge colorings 75 20 Strongly regular graphs 78 21 Moore graphs 80 22 Kneser graphs 86 A More topology 92 0 Preliminaries We assume that the reader is familiar with the rudiments of set theory including the notations z E X to indicate that z is an element of the set X and z X to indicate that it is not and the use of expressions such as x E R i z gt 1 which denotes the set of all real numbers greater than 1 We recall here some but not all of the ideas the reader should have encountered Two sets are equal iff they have exactly the same elements There is a unique set with no elements the empty set 0 We use the notation X Q Y to indicate that X is a subset on that is that z E X implies z E Y We have X Y iffX Q Y and Y Q X We use X C Yto indicatethat X is a proper subset of Y that is X Q Y and X 7 Y The intersection union and difference or relative complement of sets X and Y are de ned by X Yzlz Xandm Y XUYmlm Xorz Y and XiYmlm Xandz Y respectively We follow the standard mathematical convention that or is used inclusively so that X O Y Q X U Y The Cartesian product X x Y is the set of all ordered pairs 44 with z E X and y E Y We deal mostly with nite sets The number of elements or cardinality of a nite set X will be denoted by We also assume familiarity with the idea of a function and a few related notions The notation f X a Y means that f is a function from the set X to the set Y that is to each element x of X is associated a unique element fz of Y Functions 1 X a Y and f X a Y are equal iff X X Y Y and fz f z for all z E X For any set X the identity function on X is the function idX or just id from X to X de ned by idXm z for all z E X If f X a Y and A Q X the image ofA under 1 is the subset fA fa l a E A of Y The function f is injective or an injection if implies m1 2 for 1 m2 6 X It is surjective or a surjection if fX Y and it is bijective or a bijection if it is both injective and surjective If f is a bijection from X to Y there is an inverse function f l Y a X de ned by f 1y z iff y fz for z E X and y E Y lff X HY and g Y a Z the compositegof X a Z is de ned by g o We also use gf to denote the composite If f X a Y is a bijection we have f 1 o f idX and f o f 1 idy The rest of this section discusses equivalence relations and partitions which the reader may not have met before A binary relation on a set X is a subset R of X x X If x y E R we say that z is related to y by R and write x Ry Typically speci c binary relations are denoted by symbols such as g gt and N rather than letters Thus formally the relation gt on the set 1 2 3 is the set 2 1 3 1 3 2 of ordered pairs Let R be a binary relation on X 1 R is reflexive if m R m for all m E X 2 R is symmetric if x B y implies y R z for z y E X 3 R is transitive if x B y and y R 2 imply x R z for m y and z E X An equivalence relation is a relation that is re exive symmetric and transi tive If R is an equivalence relation on X and z E X the equivalence class of z is the set of all y E X such that x B y Example 01 The equality relation on any set is an equivalence relation and Example 02 On the set R of real numbers the relation is re exive and transitive but not symmetric Example 03 On the set R the relation lt is transitive but neither re ex ive nor symmetric Example 04 If n is a positive integer the relation of congruence modulo n on the set Z of all integers is de ned by a E 1 mod n if n divides a 7 b It is an equivalence relation and a qn a q E Z The distinct equivalence classes are 0 1 n 7 1 which we shall sometimes denote just by O 1 n 7 1 The set of equivalence classes will be denoted by Zn a notation that annoys some algebraists of my acquaintance who prefer Zn or ZnZ We de ne operations of addition and multiplication on 2 by j and It is left to the reader to verify that these are well de ned operations They satisfy many of the usual laws of arithmetic commutativity associativity distributivity those who have met the concept will know that they give Zn the structure of a ring At one point we shall need the operation of addition on 22 x 22 de ned in the obvious way a b c d a c b 1 Proposition 05 Let R be an equivalence relation on a set X and m y EX Thenx E m and i mRy Proof First z E because R is re exive Second if then y E z so zRy Finally suppose zRy lf 2 E then sz so mRz by transitivity This gives 2 E z and so Q By symmetry of B y R z so also ml E u that 18 ml M D A partition of a set X is a collection of disjoint non empty subsets of X whose union is X Proposition 06 Let X be a set 1 The collection of equivalence classes under any equivalence relation on X is a partition of X 2 Every partition of X is the collection of equivalence classes for a unique equivalence relation on X Proof 1 Let R be an equivalence relation on X and P the set of equiv alence classes under R The relation z E of Proposition 05 shows that the elements of P are non empty and have union X Suppose and are elements of P that are not disjoint Let 2 E Then x R z and y R 2 so by Propsition 05 Thus P is a partition of X 2 Let P be a partition of X and for z E X let be the unique element of P containing X By Proposition 05 if P is the set of equivalence Figure 1 The Petersen graph classes for an equivalence relation R then x R g iff g which proves the uniqueness part To prove existence de ne a relation R by x R y if z It is trivial to check that R is an equivalence relation We must show that the equivalence class is equal to Suppose y E Then z y and since y E by de nition y E Conversely if y E x then since also y E y and are not disjoint Hence y so mRyandyEM El 1 Graphs De nition 11 A graph G is a pair V E where V is a non empty nite set and E is a set of unordered pairs of elements of V The elements of V are called the vertices of G and the elements of E are the edges of G We always assume that V O E 0 We can represent a graph pictorially as in Figure 1 The dots represent the vertices and each edge u v is represented by an arc connecting the dots corresponding to the vertices u and 12 We will usually write up instead of uv of course an vii The set of vertices of a graph G may be written VG the number lVGl of vertices is the order of G denoted by nG or just n The set of edges may be written EG the number of edges is the size of G denoted by mG or just m By de nition n gt 0 but in 0 is allowed If n 1 and so in 0 G is trivial In general 0 g m g nn 7 12 If m 0 we have an empty graph while if m we have a complete graph see Figure 2 for an example Vertices u and v of a graph G are adjacent if m E EG an edge e up is incident with the vertices u and v and distinct edges e and f are adjacent if there is a vertex incident with both of them Vertices u and v are independent if Figure 2 The complete graph on 5 vertices u 7 v and uv If u and v are adjacent we shall also say that u and v are neighbors De nition 12 Let G1 and G2 be graphs An isomomhz39sm from G1 to G2 is a bijection j VG1 a VG2 such that M E EG1 iff gtuv E EG2 Here we are using the standard notation for the image of a set under a function gtuv gtuv gtu gtv gtu gtv If there exists an isomorphism G1 a G2 G1 is isomomhz39c to G2 written G1 E G2 Note that any graph is isomorphic to itself if G1 E G2 then G2 E G1 and if G1 E G2 and G2 E G3 then G1 E G3 One is tempted to say that isomorphism is an equivalence relation on the set of graphs However there is no such thing as the set of all graphs lsomorphism is an equivalence relation on any set of graphs lsomorphic graphs are essentially the same they differ only in the names of their vertices Some authors use G1 G2 to mean that G1 and G2 are isomorphic but I prefer to reserve the equal sign for well equality Nevertheless I do follow the universal practice of referring to the Petersen graph or the complete graph on n vertices meaning some one of a collection of isomorphic graphs The complete graph on n vertices will be denoted by Kn Sometimes we wish to determine the number of graphs in a given collec tion and the question arises as to whether we are counting the graphs up to identity or up to isomorphism We adopt a convention that should be clear from the following example If X is a given set of n elements the number of graphs with vertex set X77 or on X means precisely what it says the number of collections of unordered pairs of elements of X which is However the number of graphs of order n or on n vertices means the maximum number in a collection of pairwise non isomorphic graphs of order n or equivalently the number of isomorphism classes in the set of all graphs on a xed set of size n This number has no known formula the reader may care to verify that the numbers of graphs of orders 1 2 3 4 and 5 are 1 2 l G1 G2 G3 I I G1 G2 G3 Figure 3 The graphs of order 4 and size 3 4 11 and 34 respectively For order 5 particularly you may want to use the following de nition to reduce the tedium De nition 13 The complement of a graph G is the graph G with V VG in which for distinct vertices u and u up 6 EC iff up EG Put another way if K is the complete graph with vertex set VG EC 7 For example the complement Kn of the complete graph on n vertices is the empty graph on n vertices If G has order n and size m then G has size 7 m A graph is self complementary if G G If this is so we must have 2m so is even which happens iff n E 0 or 1 mod 4 In fact for any such n there exist self complementary graphs of order n For n 4 the size must be 3 In Figure 3 the top row shows all graphs of order 4 and size 3 while the bottom row shows their complements We see that G1 and G3 are up to isomorphism complements of each other while G2 is self complementary The degree of a vertex v of a graph G is the number of vertices adjacent to 1 It is denoted by degGv or just deg 12 With this de nition we can nally state a theorem Theorem 14 Let G be a graph of size m Then EvaG degv 2m Proof We can count the number p of pairs 12 e where v is a vertex of the edge e in two ways First there are m edges each with two vertices so p 2m Second the vertex v is incident to degv edges so p EvaG deg 12 E A vertex is called even or odd according as its degree is even or odd Corollary 15 Any graph contains an even number of odd vertices D The minmum degree of the vertices of a graph is denoted by 6G and the maximum by AG Clearly 0 6G AG nG71 A vertex of degree 0 is an isolated vertex while one of degree 1 is an end vertex lf 6G AG then G is regular if the common value is d C is d regular or regular of degree d A 3 regular graph is also called a cubic graph The complete graph Kn is n 7 1 regular and the Petersen graph of Figure 1 is cubic For a regular graph any two of the order n the size in and the degree 1 determine the third by the equation 2m not A subgraph of a graph G is a graph H with VH Q VG and Q We write H Q G If U is any proper subset of VG G 7 U is the subgraph obtained by deleting all vertices of U and all edges with at least one vertex in U When U u we abbreviate G7 to G7u Similarly if F is a subset of EG G7F is the subgraph obtained by deleting the edges of F and G7 e is written as G7e This notation is logically indefensible since an edge is a set of vertices Nevertheless for an edge e uv u v we adopt the convention that G 7 e and G 7 uv denote G with just an edge deleted and G 7 u v denotes G with two vertices and all incident edges deleted Note that VG 7 F VG and F EG is allowed with G 7 EG being the empty graph on VG A spanning subgraph of G is a subgraph of the same order ie containing all the vertices of C These are precisely the subgraphs of the form G7 F for F Q If u and v are independent vertices of G and f uv the graph G f has vertex set VG and edge set EG U If U is a non empty set of vertices of the graph G the subgraph ltUgt induced by U is the subgraph with vertex set U and edge set consisting of all edges of G with both vertices in U A vertex induced subgraph or just an induced subgraph is a subgraph of this form If F is a non empty set of edges of G the subgraph induced by F is the subgraph with vertex set all vertices of edges of F and edge set F An edge induced subgraph is a subgraph of this form Theorem 16 Konig 22 Let G be a graph and d an integer with d 2 AG Then there is a d regular graph containing G as an induced subgraph Proof The proof is by induction on d 7 6G If this is O G is d regular and there is nothing to do lf 1 gt 6G let G be another copy of G and form H by adding edges joining each vertex of G of degree 6G to the corresponding vertex of G Then H contains G as an induced subgraph and has 6H 6G 1 and AH d The result follows 1 The graph constructed in this proof is generally not of minimal order

### 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

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### 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.