15-344/Classnotes for Tuesday September 15

DBN: Classes: 2015-16: 15-344 / Navigation Welcome to Math 344! Edits to the Math 344 web sites no longer count for the purpose of good deed points. # Week of... Notes and Links 1 Sep 14 About This Class, Day One Handout, Tuesday, Hour 3 Handout, Thursday, Tutorial 1 Handout 2 Sep 21 Tuesday, Tutorial 2 Page 1, Tutorial 2 Page 2, Thursday, HW1 3 Sep 28 Tuesday, Class Photo, Tutorial 3 Page 1, Tutorial 3 Page 2, Thursday, HW2 4 Oct 5 Tuesday, Drawing [math]\displaystyle{ n }[/math]-cubes, Thursday, HW3 5 Oct 12 Tuesday, Tutorial Handout, Thursday, HW4 6 Oct 19 Tuesday, Tutorial Handout, Thursday 7 Oct 26 Term Test on Tuesday, Dijkstra Handout,Thursday,HW5 8 Nov 2 Tuesday, Tutorial Handout, Thursday, HW6, Sunday November 8 is the last day to drop this class 9 Nov 9 Monday-Tuesday is UofT Fall Break, Thursday, HW7 10 Nov 16 Tuesday, Thursday, HW8 11 Nov 23 Tuesday, Thursday, HW9 12 Nov 30 Tuesday, Thursday, HW10 13 Dec 7 Tuesday, FibonacciFormula.pdf, semester ends on Wednesday - no class Thursday F Dec 11-22 The Final Exam Register of Good Deeds Add your name / see who's in!

We mostly went over Day One Handout today.

Dror's notes above / Students' notes below

Lecture Note for September 15

DEFINITION 1 Graph A graph [math]\displaystyle{ G = (V,E) }[/math] is a set [math]\displaystyle{ V = \{a,b,...\} }[/math] (usually finite, "vertices") along with a set [math]\displaystyle{ E = \{(ab),(bc),(bd),...\} }[/math] ("edges") of unordered pairs of distinct elements of [math]\displaystyle{ V }[/math].

DEFINITION 2 Incident If an edge [math]\displaystyle{ e = (ab)\in{E} }[/math], we say that [math]\displaystyle{ e }[/math] is incident to [math]\displaystyle{ a }[/math] and [math]\displaystyle{ b }[/math].

DEFINITION 3 N-valent In a graph [math]\displaystyle{ G = (V,E) }[/math], a vertex [math]\displaystyle{ u \in{V} }[/math] is called bivalent if it is incident to precisely two edges and n-valent if incident to precisely n edges, where [math]\displaystyle{ n = 0,1,2,.. }[/math].

DEFINITION 4 Edge Cover An edge cover for graph [math]\displaystyle{ G = (V,E) }[/math] is a subset [math]\displaystyle{ C\subset{V} }[/math] such that every edge of [math]\displaystyle{ G }[/math] incident to at least one vertex in [math]\displaystyle{ C }[/math].

DEFINITION 5 Independent Let [math]\displaystyle{ G = (V,E) }[/math] be a graph. A subset [math]\displaystyle{ I\subset{V} }[/math] is called independent if whenever [math]\displaystyle{ a,b\in{I} }[/math], then [math]\displaystyle{ (ab)\notin{E} }[/math].

THEOREM 1 Edge covers are complementary to independent sets. In other words, [math]\displaystyle{ C\subset{V} }[/math] is an edge cover if and only if the complementary subset [math]\displaystyle{ V-C }[/math] is an independent set.

Proof [math]\displaystyle{ (\rightarrow) }[/math] Assume [math]\displaystyle{ C }[/math] is an edge cover. I assert that [math]\displaystyle{ I = V-C }[/math] is independent. Indeed, if [math]\displaystyle{ e=(ab)\in{E} }[/math], then since [math]\displaystyle{ C }[/math] is an edge cover, either [math]\displaystyle{ a\in{C} \implies a\notin{I} }[/math] or [math]\displaystyle{ b\in{C} \implies b\notin{I} }[/math], which implies [math]\displaystyle{ a,b }[/math] are not connected.

[math]\displaystyle{ (\leftarrow) }[/math] Assume [math]\displaystyle{ I=V-C }[/math] is independent. Pick any edge [math]\displaystyle{ e = (ab)\in{E} }[/math]. As [math]\displaystyle{ I }[/math] is independent, [math]\displaystyle{ (ab) }[/math] does not connect [math]\displaystyle{ a,b }[/math]. Hence, either [math]\displaystyle{ a\notin{I} \implies a\in{C} }[/math] or [math]\displaystyle{ b\notin{I} \implies b\in{C} }[/math], which implies [math]\displaystyle{ e }[/math] is incident to an element of [math]\displaystyle{ C }[/math]. QED