-1+1406 
Introduction to Graph Theory and Applications

Loosely speaking, graphs are basically a set of objects, or vertices (nodes), taken together with a set of inter-node relationships, called edges. Graph theory is a relatively new area of mathematics that has recently become increasingly popular due to its far reaching spectrum of use. Its oigins were in daily applications to bridge routes and chess and its study preserves this practice. Graph theory is different in the sense that one can both color with crayons and do a proof by induction all in one day's work, which is one reason why it has been often labelled as one of the more fun and enjoyable aspects of mathematics!

Graphs as mathematical objects form the basis of our study, a continuing investigation whose beginnings go back to the great mathematician Leonhard Euler. We will begin our study there and build our way up to modern aspects and applications of graph theory.

Lectures
  1. Lesson 1: What is a graph?

    This lecture is the opening lecture in the Introduction to Graph Theory series. It is a very rough basic overview of some introductory material we will need to know for future lessons.

    We are following (almost exactly) the Graphs & Digraphs, Fifth Edition book by Gary Chartrand, Linda Lesniak, and Ping Zhang. This video covers the opening chapter.

    Length: about 1 hour. We want to make a special note that this is the first video we have ever edited and made, especially in the way of teaching. We are open to constructive criticism, as we want you guys to be able to learn from this! We are using a Wacom Bamboo tablet to capture our writing, and Camtasia software to record on screen. If you guys have any suggestions, we want to hear them before we make too many of these videos! :D

  2. Lesson 2: Degrees in Graphs (Sequences)

    Lesson 2 covers topics such as degree sequences, the Havel-Hakimi theorem and algorithm, the Erdos-Gallai Theorem, and the "Party Problem"!

    We have also greatly improved the teaching methods in Lesson 2. Hopefully you guys will enjoy this one more, and you'll learn something, too!

  3. Lesson 3: Paths, Cycles, and Periphery

    Lesson 3 covers topics such as walks, paths, cycles, circuits, distance, adjacency matrices, and periphery!

    We are still using the improved lecture method here. This video is about 30 minutes long. Enjoy!

Prerequisites

In terms of mathematical prerequisites, experience with Combinatorics, Number Theory, or just general Discrete Mathematics is ideal. There will be logic involved, and proof methods, so any experience with that is good as well. There may be a few summations here and there, but no integrals, gradients, derivatives, or topological spaces will be involved.

We want to make this accessible to everyone, so if needed we can definitely explain!

Syllabus

Alright, guys, tentative syllabus is up! Please remember that I want to be really flexible with this class, and if I get requests for more material on certain subjects, we can omit the probabilistic stuff at the end, or edit the syllabus in the middle as we need to!

Materials will be hosted on this University of Reddit site and on the accompanying subreddit, r/IntroToGraphTheory. We are going to try to cover many bases here, and the syllabus will be subject to change. We will do at least one lesson a week covering the materials listed, so check in regularly!

(Also, keep in mind, even though I don't post applications of sections in the syllabus, I plan on covering applications at least briefly in every section, when applicable.)

Week 1: An Introduction to Graphs and Digraphs.

  • Graphs
  • Degree Sequence
  • Graph Isomorphisms
  • Subgraphs
  • Connected Graphs and Distance
  • Digraphs and Multigraphs

Week 2: Trees and Connectivity

  • Nonseparable Graphs
  • Spanning Trees
  • Connectivity and Edge Connectivity
  • Menger's Theorem

Week 3: The Structure of Graphs

  • Bridges, Cut-Vertices, and Blocks
  • The Graph Reconstruction Conjecture

Week 4: Eulerian and Hamiltonian Graphs

  • Eulerian Paths and Cycles
  • Hamiltonian Paths and Cycles

Week 5: Planarity

  • The Euler Identity
  • What is planarity, and what is nonplanarity?
  • Hamiltonian Planar Graphs

Week 6: Graph Colorings

  • Vertex Colorings
  • Edge Colorings

Week 7: Matchings, Factors, and Decompositions

  • Matchings and Independence in Graphs
  • Factorizations and Decompositions
  • Graph Labelings

Week 8: Domination in Graphs

  • The Domination Number of a Graph
  • Independent Domination
  • Other Domination Parameters

Week 9: Ramsey Theory

  • Classical Ramsey Numbers (Not sure what else in Ramsey Theory we'll cover here, tentative for now!)

Week 10: The Probabilistic Method in Graphs

  • The Probabilistic Method
  • Random Graphs
Additional information

Message us anytime if you have any questions!!

Teacher qualifications

My fiance and I are senior mathematics majors at a relatively small university in the USA where the mathematics faculty puts emphasis on discrete mathematics. We have done a good deal of mathematics research in number theory, probabilistic methods, and graph theory and hope to each have about five publications by graduation, pending acceptance, of course! Additionally, each of us have presented our research at national conferences including the Joint Meetings in Mathematics, MathFest, and smaller regional conferences. We have taken undergraduate graph theory, combinatorics, number theory, and abstract algebra courses (not counting the others we've taken!) and we have both tutored in each area. We're just trying to get more people interested in mathematics and hopefully inspire a few folks!

Latest Update
Lesson 3 is now live! (2012-09-10 23:06:44)

"We are just informing everyone that Lesson 3 is now live. It can be accessed here: http://www.youtube.com/watch?v=5NkitNa5PHg or through the University of Reddit page/official subreddit page.

This lesson covers paths, cycles, circuits, adjacency matrices, distance, and periphery. Hopefully this lesson puts us closer to wrapping up our lessons from Week 1.

Enjoy!

peecatchwho

potato_fish"

Roster
1. peecatchwho
2. as696
3. bonzi24
4. reeve512
5. cruizen
6. bergm
7. Kivrin
8. Daza123
9. violaep
10. letmefinish
11. ajreyn
12. miku
13. zarea
14. najera_
15. rosman
16. rahul67
17. alexkarp
18. spqr11
19. FoffT
20. N0tAUsername
21. ravikarna27
22. mattystoopy
23. lionbologna
24. Da_Top_Dawg
25. cupofchupchups
26. guth90
27. cheesegreyter
28. MillsMJ
29. wolfearth
30. joecapps1127
31. lixardz
32. skadamat
33. WhyBotWhy
34. whywork7
35. tjalve
36. anvil
37. urswap
38. codementum
39. limxinf
40. metalliska
41. maddy1907
42. elurin
43. 5outh
44. wickedsweetcake
45. wickedsweetcake
46. Catalanist
47. Wardini
48. h2p_2015
49. idontgetmemes
50. rorschach122
51. Gilgamesh
52. samhmariam
53. smooochy
54. thoradam
55. danskete
56. dieek
57. mattroe
58. narf
59. danielsmw
60. Ivansek
61. RuNZ
62. grungleshnorts
63. smadley
64. infinite_series
65. Ridiculous
66. lemonizer
67. soulgrocery
68. flojito
69. nielse63
70. forgotmybloodyname
71. msciab
72. marchdown
73. floatingdecimal
74. bakara
75. Apage43
76. ihibanez
77. astrokid
78. Althaine
79. bbohnet
80. ihusker_42
81. decenteredlife
82. theavatare
83. arnorb
84. Mamemoo
85. seakun
86. pianoplayer98
87. lingrush
88. lecafard
89. ryelacey
90. ahodges
91. ashcairo
92. RobinZXu
93. Sarhan
94. Toepuka
95. shai251
96. meetchboris
97. drphrink
98. spearhard
99. bigfatyak
100. partkyle
101. eben23
102. kurin
103. feanor
104. buildafriend
105. wutugu
106. rpgcubed
107. sw0rdz
108. qmynd
109. chacunlesena
110. ayeema
111. gebeverungen
112. mishkaechoes
113. zombiebeethoven
114. syrups
115. deathmagic87
116. JonStark
117. andrewdanks
118. amalbose
119. ddkkim
120. cgront
121. sirachman
122. mathboss
123. protossible
124. farcus
125. ryanlabouve
126. r4gnar0k
127. danierX
128. Bezout
129. songanddanceman
130. krangbull
131. varghese1990
132. eckrause
133. bldnola
134. trompwnerer
135. Absorbtive
136. sudo-nebula
137. danran
138. dtmetz
139. menedemus
140. buttercrackers
141. JAKarpis
142. gfixler
143. beamish14
144. neptr
145. MoreThanLuck
146. MoreThanLuck
147. LethalLink
148. LegendaryZ
149. five35
150. svraghavan
151. 253F584C
152. itsaguytalking
153. svacha
154. xspeedcruiser
155. DIRTYBRIEFS
156. western_schmoobris
157. rickytijerina
158. math
159. sgtHulka
160. ben7005
161. phi4theory
162. TheSnowKing
163. kwojcik
164. mooglefrooglian
165. Thewindpickedup
166. kamps.duac
167. chngr
168. donaldruok
169. Mwebaze
170. Superfish
171. celestec
172. panflip
173. pretendperson
174. RowanRoseHeart
175. wydell
176. SubmitQuery
177. obsidianight
178. 4thguy
179. chaos0
180. umlaut_again
181. galaris
182. moomin42
183. Mick
184. onehundredseven
185. ziptnf
186. 404TrainNotFound
187. timeinvariant
188. sensei_von_bonzai
189. b_griffon
190. continuity
191. mghazal
192. AquaBlue
193. jsvana
194. chycachrrycola
195. loweschmidt
196. Driver1676
197. Shlldn
198. kyzic
199. PlutoniumDragon
200. mohnish
201. coco
202. 0m1cr0n
203. dunecn
204. zerubroberts
205. Nella
206. bhaff
207. liverb
208. abeyaar
209. nazz007online
210. orangejuice982
211. bluepickles
212. nitellubv
213. rdm5181
214. randomman289
215. Augs
216. kapax
217. PalmPaperCut
218. elaufis
219. jmank88
220. sriracha5
221. salisbury.joseph
222. davikrehalt
223. matteyes
224. coolsmith3991
225. jucanya
226. aTroll
227. Clammy
228. commanderblingbling
229. justwantanaccount
230. EnergyHobo
231. SunSatION
232. hokiefan13
233. potato_fish
234. antu82
235. votecthulhu
236. aeonian
237. eadlam
238. richardgarciajr
239. JDragon
240. Hbou
241. Farce
242. longringfinger
243. katj93
244. jetblackswan
245. oneblueham
246. liutanyu
247. 1729
248. arktemplar
249. razuge
250. trashpile
251. jordanbray
252. kchar
253. probablytom
254. bob
255. soumitrabhat
256. limlom
257. pg1770
258. baloghr
259. elberethf
260. _hst
261. Axol0tl
262. AtlasAnimated
263. clayt0n
264. dmanww
265. wangxian
266. AresYolk
267. jamesmcm
268. singdawg
269. maverickrhetoric
270. quinn_winters
271. nirajanrk
272. CRichelieu
273. profryan
274. strngr11
275. mortsemious
276. integratedc
277. whinycat
278. irene
279. zokusuji
280. thewatersabove
281. cbradbur
282. TheVoluntarist
283. allachris
284. 55five55
285. guywithsmalleyes
286. band007geek
287. pvejunky12
288. S-Skyler
289. grlldcheese
290. eulersphi
291. velazqua
292. harrelious
293. GrayTShirt
294. Mystique
295. carlospruitt
296. pennacchio
297. Janus
298. gussy1z
299. xerxexrex
300. sockshoelemma
301. LGordon2
302. clembo99
303. idytgt
304. iwanttolearnmaths
305. stcollin
306. rohit_95
307. theblueprint
308. Budzoli
309. wandabee
310. ThomasM
311. thoythoy
312. rozzer
313. mikeypuff
314. palutz
315. bmerva3
316. WholeBeefOxtail
317. aliandrabusila
318. shittymath
319. sumguysr
320. wsankey
321. bhuwan
322. tobbe
323. Deltrus
324. chumofchance
325. hitnrun7
326. bigmoneyhat
327. jenetteehelena
328. vmm5596
329. Nicole
330. ejk314
331. AdamMcLean
332. basetw0
333. sloppy421
334. Buggy
335. larrylemur
336. ellomate07
337. Ophashias
338. bijan
339. mrtwiddletoes
340. devilasks
341. fattybake
342. inspiredKID
343. karoyakani
344. ryengi2
345. dstilwell
346. skittlles
347. mvpxv
348. kmate25
349. allxk
350. yahachutebya
351. kbugeja
352. mkay510
353. brightbard12-4
354. wasif_hyder
355. veganskeptic
356. Snarik
357. jrnewman42
358. ccz918
359. ikeamoah
360. proteanbeing
361. rosatryne
362. steeve149
363. tenoman
364. Campers
365. Zoccihedron
366. minasso
367. rougealevre
368. jorma75
369. Deicidus
370. qhreul
371. last_name_on_reddit
372. kevstew
373. whacko_jacko
374. stewartbutler
375. brrevans
376. lennaspam
377. danedaworld
378. oberyn
379. jigglypuff_apnea
380. cbun
381. cpryby
382. llcooldre
383. theansweris7
384. Mulien
385. spencerutt
386. Futurephysicist
387. zbadgett
388. do_you_hate_me
389. knudLeopold
390. jcrubino
391. acasadonte
392. bigjust
393. AmundsenJunior
394. Goondor
395. bayofpigs61
396. simple_song
397. ashwin
398. Sethionic
399. Doctor
400. LuminiferousEther
401. insertfunnynamehere
402. Trkrtrk
403. Somatostatin
404. qzpmwxin
405. totocus
406. bulbul
407. chinsi
408. Omi
409. blfang
410. saputello
411. burp3141
412. moosebot
413. kamaos5
414. mimo8080
415. Islambekm
416. scroompa
417. GGMUDarc
418. ctwiz
419. somehokie
420. gaolathe
421. swapex
422. senusert
423. behyeefatt
424. Grammr
425. zentropia
426. cowzzwoc
427. shalombi
428. srslySHENANIGANS