### Create a StudySoup account

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

Already have a StudySoup account? Login here

# GRAPH THEORY I MATH 776

GPA 3.51

### View Full Document

## 86

## 0

## Popular in Course

## Popular in Mathematics (M)

This 7 page Study Guide was uploaded by Cassidy Grimes on Monday October 26, 2015. The Study Guide belongs to MATH 776 at University of South Carolina - Columbia taught by J. Cooper in Fall. Since its upload, it has received 86 views. For similar materials see /class/229523/math-776-university-of-south-carolina-columbia in Mathematics (M) at University of South Carolina - Columbia.

## Reviews for GRAPH THEORY I

### 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/26/15

GRAPH THEORY STUDY GUIDE 1 DEFINITIONS De nition 1 Partition of A A set A A17 Ak of disjoint subsets of a set A is a partition of A if UA of all the sets Ai E A and Ai 3e 0 for every i De nition 2 Vertex set The set of vertices in a graph denoted by VG De nition 3 Edge set The set of edges in a graph denoted by De nition 4 Order the number of vertices of a graph G written De nition 5 Incident A vertex v is incident with an edge e if v 6 67 then 6 is an edge at 1 De nition 6 Adjacent Two vertices my of G are adjacent if my is an edge of G De nition 7 Complete If all vertices of G are pairwise adjacent7 then G is complete De nition 8 Independent A set of vertices or edges is independent if no two of its elements are adjacent De nition 9 Isomorphic We call G and H isomorphic7 and write G 2 H7 if there exists a bijection 41sz A V with my 6 E ltgt E E for all my in V De nition 10 Property A class of graphs that is closed under isomorphism is called a graph property De nition 11 Invariant A map taking graphs as arguments is called a graph invariant if it assigns equal values to isomorphic grap s De nition 12 Induced If C Q G and G contains all the edges my 6 E with my 6 V 7 then G is an induced subgraph of G We say that V induces G in G De nition 13 Spanning C Q G is a spanning subgraph of G if V spans all of G or V V De nition 14 Line Graph The line graph LG of G is the graph of E in which m7 y E E are adjacent as vertices if and only if they are adjacent as edges in G De nition 15 the set of neighbors of a vertex v De nition 16 Degree The degree dv of a vertex v is the number of edges at v or the number of neighbors o 1 De nition 17 Isolated A vertex of degree 0 is isolated De nition 18 Minimum degree 6G is the minimum degree of G De nition 19 Maximum degree AG maximum degree of G De nition 20 Regular all the vertices of C have the same degree 16 then G is kregular7 or regular De nition 21 Average degree dG Evev dv and 6G S dG S AG De nition 22 Number of Edges Evev dv dG 6 De nition 23 Path A path is a nonempty graph P V7 E of the form V m0m1mk and moml7 mk1mk where the mi are all distinct De nition 24 H path Given a graph H7 we call P an Hpath if P is nontrivial and meets H exactly in its end points De nition 25 Cycle If P m07 mk1 is a path and k 2 37 then the graph C P mk71m0 is called a cycle De nition 26 Girth The minimum length of a cycle in a graph G is the girth De nition 27 Circumference The maximum length of a cycle in G is its circumference De nition 28 Chord An edge which joins two vertices of a cycle but is not itself an edge of the cycle is a chord of the cycle De nition 29 Induced cycle an induced cycle in G a cycle in G forming an induced subgraph is one that has no chords De nition 30 Distance The distance dg 17 y in G of two vertices z y is the length of a shortest z 7 y path in G De nition 31 Diameter The greatest distance between any two vertices in G is the diameter of G denoted by diam G De nition 32 Central a vertex is central in G if its greatest distance from any other vertex is as small as possible De nition 33 Radius the greatest distance between the central vertex and from any other vertex denoted rad G where radG minxewg maxyewg dg 17 y where radG S diamG S 2radG De nition 34 Walk A walk of length k is a nonempty alternating sequence of vertices and edges in G De nition 35 Connected A nonempty graph G is called connected if any two of its vertices are linked by a path in G De nition 36 Component A maximal connected subgraph of G is called a component De nition 37 Separator lf A7 B C V and X E V U E are such that every A 7 B path in G contains a vertex or an edge from X7 we say that X separates the set A and B in G De nition 38 Cutvertex A vertex which separates two other vertices of the same component is a cutver tex De nition 39 Bridge An edge separating its ends is a bridge De nition 40 lsconnected G is called kconnected if lGl gt k and G7X is connected for every set X E V with le lt Is No vertices of G are separated by fewer than k other vertices De nition 41 Connectivity The greatest integer k such that G is kconnected is the connectivity7 HG De nition 42 ledge connected lf lGl gt 1 and G 7 F is connected for every set F E E of fewer than 1 edges7 then G is called ledge connected De nition 43 Edgeconnectivity The greatest integer 1 such that G is ledge connected is MG De nition 44 Forest An acyclic7 g raph7 one not containing any cycles is called a forest De nition 45 Tree A connected forest is called a tree De nition 46 Leaf The vertices of degree 1 of a tree De nition 47 Treeorder Writing 1 2 y for z E TTy then de ne a partial ordering on VT7 the tree order associated with T and 7 De nition 48 Normal Tree A rooted tree T contained in a graph G is called normal in G if the ends of every Tpath in G are comparable in the tree order of T De nition 49 R partite A graph G V7 E is called Tpartitie if V admits a partition into 7 classes such that every edge has its ends in different classes De nition 50 Complete Partite An Tpartite graph in which every two vertices from different partitions classes are adjacent is called complete De nition 51 Contraction Let 6 my be an edge of the graph C By Ge we denote the graph obtained from G by contracting the edge 6 into a new vertex v8 De nition 52 Minor If G MX is a subgraph of another graph Y we call X a minor of Y De nition 53 Eulerian A closed walk in a graph is an Euler tour if it traverses every edge of the graph exactly once Its called Eulerian if it admits an Euler tour De nition 54 Vertex Space The vertex space of G is the vector space over the 2element eld of all functions V A F2 VG De nition 55 Edge Space The function E A F2 form the edge space of G G De nition 56 Cycle Space The cycle space is the subspace of the edge space spanned by all the cycles in G C CG De nition 57 Cut Space The cut edges of G form a subspace of G denoted by Cquot De nition 58 Hypergraph A hypergraph is a pair V7 E of disjoint sets7 where the elements of E are nonempty subset of any cardinality of V De nition 59 Directed A directed graph is a pair V7 E of disjoint set of vertices and edges together with two maps init E A V and ter E A V assigning to every edge e an initial vertex inite and a terminal vertex tere De nition 60 Orientation A directed graph D is an orientation of an undirected graph G if VD VG andED EF and if initetere Ly for every edge e my De nition 61 Multigraph A multigraph is a pair E of disjoint sets of vertices and edges together with a map E A U V2 assigning to every edge either one or two vertices its ends De nition 62 Matching A set M of independent edges in a graph G VEis called a matching De nition 63 Factor A kregular spanning subgraph is called kfactor De nition 64 Alternating Paths A path in G which starts in A at an unmatched vertex and then contains7 alternatelyedges from E 7 M and from M7 is an alternating path with respect to M De nition 65 Augmenting Path An alternating path P that ends in an unmatched vertex of B is called an augmenting path De nition 66 Cover Let us call a set U E V a vertex covering of E if every edge of G is incident with a vertex in De nition 67 Given a graph G let us denote by C3 the set of its components and by qG the number of its odd components7 those of odd order De nition 68 Block A maximal connected subgraph without a cutvertex is called a block De nition 69 Plane Graph Graph drawing in the plane De nition 70 Planar If G can be drawn in the plane without a crossing7 G is plannar De nition 71 Frontier The frontier of a set X E R2 is the set Y of all points y E R2 such that every neighborhood of y meets both X and R2 7 X De nition 72 Geometric Graph A Geometric Graph is a planar embedding of G with straight lines De nition 73 Topological lsomorphism We call a a topological isomorphism between H and H plane graphs if there exists a homeomorphism g0 S2 A S2 such that 1 2 7r 0 so c 7r 1 induces a on V U E De nition 74 Combinatorial lsomorphism a can be extended to an incidence preserving map a V U E U F A V U E U F preserves incidence of not only vertices and edges but also of vertices and edges with faces De nition 75 Graph Theoretical lsomorphism a is a graph theoretical isomorphism of plane H and H if0Hlfl I f 6 F H lf l I f 6 Fl De nition 76 Simple We call a subset f of a graph7s edge space G simple if every edge of G lies in at most two sets of f De nition 77 Visible Given a polygon P7 vertices w7 v7 w is visible from v7 if line segment W U W ll De nition 78 Plane Multigraph A plane multigraph is a pair G E of nite sets of vertices and edges7 respectively satisfying the following conditions 1 V g R2 2 every edge is either an arc between two vertices or a polygon containing exactly one vertex its endpoints 3 apart from its own endpointss7 and edge contains no vertex and no point of any other edge De nition 79 Plane Dual A plane dual Vi7 Equot G if there are bijections F 7gt Vquot7 E 7gt E 7 V 7gt F 7 where f gt gt v e gt gt equot7 v gt gt f v satisfying the following conditions 1 i vv E f for all f E F 2 le Cl le el le C l 1 for all e E E7 and in each of e and e this point is an inner point of a straight line segment 3 v E for all v E V De nition 80 Proper coloring lf cv a cw for all v adjacent w7 then c is a proper coloring De nition 81 lscolorable G is hcolorable if there exist proper coloring of the vertices with h colors De nition 82 hedgecolorable G is hedgecolorable if there exists a proper edge coloring with h colors or proper coloring of line graph LG De nition 83 minimum h so that G is hcolorable or chromatic number of G De nition 84 XG minimum h so that G is hedge colorable or chromatic index of G De nition 85 c 1j color class of all the vertices colored j De nition 86 hconstructible For each h E N let us de ne the class of kconstructible graphs recursively as follows 1 Kk is hconstructible 2 If G is hconstructible and Ly E VG are nonadjacent7 then also G is hconstructible 3 If G1 G2 are hconstructible and there are vertices z yl yg such that Gl Gg and zyl E EG1 and my 6 EG27 then also G1 U G2 7 zyl 7 my ylyg is hconstructible 2 THEOREMS Proposition 87 The number of vertices of odd degree in a graph is always even Proposition 88 Every graph G with at least one edge has a subgraph H with 6H gt H 2 6G Proposition 89 Every graph G contains a path of length 6G and a cycle of length at least 6Gl provided that 6G 2 2 Proposition 90 Every graph G containing a cycle satis es gG S 2diamG 1 Proposition 91 A graph G of radius at most k and maximum degree at most d 2 3 has fewer than ddjd 7 1k vertices Theorem 92 Let G be a graph If dg 2 d 2 2 and gG 2 g E N then lGl 2 n0d7 g where n0dg 1 d01d 71i ifg 2r 1 is odd 2213d71i ifg 2r is even Corollary 93 If 6G 2 3 then gG lt 2loglGl Proposition 94 The vertices of a connected graph G can always be enumerated say as v17 vn so that Cl Gv17 vi is connected for every i Proposition 95 If G is nontrivial then HG g MG g 6G Theorem 96 Let 0 f h E N Every graph G with dG 2 4h has h lconnected subgraph H such that H gt 6G 7 h Theorem 97 The following assertions are equivalent fr a graph T 1 T is a tree 2 Any two vertices of T are linked by a unique path in T 3 T is minimally connected ie T is connected by T 7 e is disconnected for every edge e in T 4 T is maximally acyclic ie T contains no cycle but T xy does for any tow nonadjacent vertices x y E T Corollary 98 The vertices of a tree can always be enumerated say as v1 M vn so that every vi with i 2 2 has a unique neighbor in v1 M vn11 Corollary 99 A connected graph with n vertices is a tree and only if it has n 7 1 edges Corollary 100 If T is a tree and G is any graph with 6G 2 1T1 7 1 then T Q G ie G has a subgraph isomorphic to T Lemma 101 Let T be a normal tree in G 1 Any two vertices x y in T are separated in G by the set 2 If S Q VT VG and S is downclosed then the components of G 7 S are spanned by the sets m with x minimal in T 7 5 Proposition 102 Every connected graph contains a normal spanning tree with any speci ed vertex as its root Proposition 103 A graph is bipartite and only if it contains no odd cycles Proposition 104 1 Every TX is also an MX thus every topological minor of a graph is also its or inary minor 2 If AX S 3 then every MX contains a TX thus every minor with maximum degree at most 5 of a graph is also its topological minor Proposition 105 The minor relation lt and the topological minor relation are partial orderings on the class of nite graphs ie that are reflexive antisymmetric and transitive Theorem 106 A connected graph is Eulerian and only Every vertex has even degree Proposition 107 The induced cycles in G generate its entire cycle space Proposition 108 The following assertions are equivalent for edge set F E E 1 F E CG 2 F is a disjoint union of edge sets of cycles in G 3 All vertex degrees of the graph VF are even Proposition 109 Together with Z the cuts in G form a subspace Cquot of 5 This space is generated by cuts of the form Lemma 110 Every cut is a disjoint union of bonds Theorem 111 The cycle space C and the cut space Cquot of any graph satisfy C C 4 and Cquot Ci Theorem 112 Let G be a connected graph and T Q G a spanning tree Then the corresponding fundamental cycles and cuts form a basis of CG and of Cquot C respectively If G has n vertices and m edges then dimCG m 7 n 1 and dimC n 71 Theorem 113 Konig The maximum cardinality of a matching in G is equal to the minimum cardinality of a vertex cover of its edges Theorem 114 Hall G contains a matching ofA and only if lNSl 2 5quot for allS Q A Corollary 115 If G is h 7 regular with h 2 1 then G has a 1factor Corollary 116 Every regular graph of positive even degree has a 2factor Theorem 117 Tutte A graph G has a 1factor and only if qG 7 S S lSlforS Q VG Corollary 118 Petersen Every bridgeless cubic graph has a 1factor Theorem 119 Every graph G E contains a vertex set S with the following two properties 1 S is matchable to Cg q 2 Every component of G 7 S is factorcritical Given any such set S the graph G contains a 1factor and only if 5 lCGsl Theorem 120 G is 2connected i either i G is a cycle or G can be obtained from a 2connected H by adding an H path Lemma 121 If G is 3connected and lGl gt 4 then G has one edge st G 7 e is 3connected Theorem 122 G is 3connected i there exists a sequence of graphs G0 M Gn such that 1 G0 K4 G7 G 2 CH1 has an edge xy with dx dy 2 3 and GI Gi1xy Vi lt n Theorem 123 Tutte The cycle space of a 3connected graph is generated by nonseparating induced cycle Theorem 124 Menger Let G V E be a graph and AB E V Then the minimum number of vertices separating A from B in G is equal to the maximum number of disjoint A 7 B paths in G Corollary 125 Let a b be distinct vertices of G 1 If ab Q E then minimum number of vertices ab separating a from b equal maximum number of independent a 7 b path 2 the minimum number of edges separating a from b in G is equal to the max number of edges disjoint a 7 paths Theorem 126 Global Menger s Theorem 1 A graph is kconnected and only if it contains k in dependent path between any two vertices 2 A graph is kedgeconnected and only it contains k edgedisjoint paths between any two vertices Theorem 127 Jordan Curve Theorem for Polygons For every polygon P E R2 the set R2 7 P has exactly two regions Each of these has the entire polygon P as its frontier Lemma 128 Let P1 P2 P3 be three arcs between the same two endpoints but otherwise disjoint 1 R2 P1 U P2 U P3 has exactly three regions with frontiers P1 U P2 P2 U P3andP1 U P3 2 IfP is an arc between a point in P1 and a point inPg whose interior lies in the region of R27 P1 UPg that contains P2 then P N P2 0 Lemma 129 Let X1X2 Q R2 be disjoint sets each the union of nitely many points and arcs and let P be an arc between a point in Xland one in X2 whose interiorP lies in a region 0 of R2 7 X1 U X2 Then OP is a region oflR2 7 X1 U P UXQ Theorem 130 Let go C1 7gt C2 be a homeomorphism between two circles on 52 let 01 be a region of C1 and let 02 be a region of C2 Then go can be extended to a homeomorphism C1 U 01 7gt C2 U 02 Lemma 131 Let G be a plane graph and e an edge of G 1 If X is the frontier of a face of G then either e E XorX N e 0 2 If e lies on a cycle C Q G then e lies on the frontier of exactly two faces of G and these are contained in distinct faces of C 3 If e lies on no cycle then e lies on the frontier of exactly one face of G Corollary 132 The frontier of a face is always the point set of a subgraph Proposition 133 A plane forest has exactly one face Lemma 134 If a plane graph has di erent face with the same boundary then the graph is a cycle Proposition 135 In a 2connected plane graph every face is bounded by a cycle Proposition 136 The face boundaries in a 3connected plane graph are precisely its nonseparating induced cyc es Proposition 137 A plane graph of order at least 5 is maximally planar and only if it is a plane trian gulation Theorem 138 Euler s Formula Let G be a connected plane graph with n vertices m edges and lfaces then n7ml 2 Corollary 139 A plane graph with n 2 3 vertices has at most 3n 7 6 edges Every plane triangulation with n vertices has 3n 7 6 Corollary 140 A plane graph contains neither K5 nor K33 as a topological minor Theorem 141 1 Every graphtheoretical isomorphism between two plane graphs is combinatorial ts extension to a face bijection is unique and only the graph is not a cycle 2 Every combinatorial isomorphism between two 2connected plane graphs is topological Proposition 142 Every two embedding of a 3connected Graph are equivalent Theorem 143 Kuratowski The following are equivalent 1 G is planar 2 G has no K5 and K33 minor 3 G has no TK5 or TK33 minor Lemma 144 Every 3connected G with no K5 or K33 minor is planar Lemma 145 Let X be a set of 3connected graphs Let G be a graph with HG S 2 and G1G2 proper induced subgraph of G such that G G1 U G2 and lGl Ggl HG If G is edge maximal with respect to not having a topological minor in x then so are G1 and G2 and G1 U G2 K2 Lemma 146 If lGl 2 4 and G is edgemaximal with respect to having no TK5 or TK33 minor then G is 3connected Theorem 147 Maclane G is planar and only if its cycle space has a simple basis Theorem 148 A 3connected graph is planar and only every edge lies on at most 2 non separating induced cyclesequivalently exactly Proposition 149 For any connected plane multigraph C an edge set E Q EG is the edge set of a cycle in G and only if Equot I e le E E is a minimal cut in Gquot Proposition 150 If G is an abstract dual of G then the cut space of G is the cycle space of G Cquot G CG Theorem 151 A graph is planar if and only it has an abstract dual Theorem 152 All planar graphs are 4colorable Theorem 153 Every planar graph is 5colourable Theorem 154 Every planar graph not containing a triangle is 3colourable Proposition 155 Every graph G with m edges satis es xG S g 2m Proposition 156 Every graph G satis es xG S colG max6Hl H E G1 Corollary 157 Every graph G has a subgraph of minimum degree at least xG 7 1 Theorem 158 Brooks Let G be a connected graph If G is neither complete nor an odd cycle then XG S NC Theorem 159 Erd s For every integer k there exists a graph G with girth gG gt h and chromatic number xG gt h Theorem 160 Hajos Let G be a graph and h E N Then xG 2 h if and only if G has a kconstructible subgraph Proposition 161 Konig Every bipartite graph G satis es x G AG Theorem 162 Vizing Every graph G satis es AG S XG S AG 1

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

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

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

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