We invite you to a fascinating journey into Graph Theory — an area which connects the elegance of painting and the rigor of mathematics; is simple, but not unsophisticated. Graph Theory gives us, both an easy way to pictorially represent many major mathematical results, and insights into the deep theories behind them.
This course is part of the Introduction to Discrete Mathematics for Computer Science Specialization
Offered By
University of California San Diego
National Research University Higher School of Economics
Introduction to Discrete Mathematics for Computer Science SpecializationUniversity of California San DiegoAbout this Course
162,095 recent views
Learner Career Outcomes
33%
started a new career after completing these courses
50%
got a tangible career benefit from this course
33%
got a pay increase or promotion
Shareable Certificate
Earn a Certificate upon completion
100% online
Start instantly and learn at your own schedule.
Course 3 of 5 in the
Flexible deadlines
Reset deadlines in accordance to your schedule.
Beginner Level
Approx. 20 hours to complete
English
Subtitles: English, Greek
Learner Career Outcomes
33%
started a new career after completing these courses
50%
got a tangible career benefit from this course
33%
got a pay increase or promotion
Shareable Certificate
Earn a Certificate upon completion
100% online
Start instantly and learn at your own schedule.
Course 3 of 5 in the
Flexible deadlines
Reset deadlines in accordance to your schedule.
Beginner Level
Approx. 20 hours to complete
English
Subtitles: English, Greek
Offered by
University of California San Diego
UC San Diego is an academic powerhouse and economic engine, recognized as one of the top 10 public universities by U.S. News and World Report. Innovation is central to who we are and what we do. Here, students learn that knowledge isn't just acquired in the classroom—life is their laboratory.
National Research University Higher School of Economics
National Research University - Higher School of Economics (HSE) is one of the top research universities in Russia. Established in 1992 to promote new research and teaching in economics and related disciplines, it now offers programs at all levels of university education across an extraordinary range of fields of study including business, sociology, cultural studies, philosophy, political science, international relations, law, Asian studies, media and communicamathematics, engineering, and more.
Syllabus - What you will learn from this course
3 hours to complete
What is a Graph?
What are graphs? What do we need them for? This week we'll see that a graph is a simple pictorial way to represent almost any relations between objects. We'll see that we use graph applications daily! We'll learn what graphs are, when and how to use them, how to draw graphs, and we'll also see the most important graph classes. We start off with two interactive puzzles. While they may be hard, they demonstrate the power of graph theory very well! If you don't find these puzzles easy, please see the videos and reading materials after them.
3 hours to complete
14 videos (Total 52 min), 5 readings, 5 quizzes
14 videos
Knight Transposition2m
Seven Bridges of Königsberg4m
What is a Graph?7m
Graph Examples2m
Graph Applications3m
Vertex Degree3m
Paths5m
Connectivity2m
Directed Graphs3m
Weighted Graphs2m
Paths, Cycles and Complete Graphs2m
Trees6m
Bipartite Graphs4m
5 readings
Slides1m
Slides1m
Slides1m
Slides1m
Glossary10m
2 practice exercises
Definitions10m
Graph Types10m
5 hours to complete
CYCLES
We’ll consider connected components of a graph and how they can be used to implement a simple program for solving the Guarini puzzle and for proving optimality of a certain protocol. We’ll see how to find a valid ordering of a to-do list or project dependency graph. Finally, we’ll figure out the dramatic difference between seemingly similar Eulerian cycles and Hamiltonian cycles, and we’ll see how they are used in genome assembly!
5 hours to complete
12 videos (Total 89 min), 4 readings, 6 quizzes
12 videos
Total Degree5m
Connected Components7m
Guarini Puzzle: Code6m
Lower Bound5m
The Heaviest Stone6m
Directed Acyclic Graphs10m
Strongly Connected Components7m
Eulerian Cycles4m
Eulerian Cycles: Criteria11m
Hamiltonian Cycles4m
Genome Assembly12m
4 readings
Slides1m
Slides1m
Slides1m
Glossary10m
4 practice exercises
Computing the Number of Edges10m
Number of Connected Components10m
Number of Strongly Connected Components10m
Eulerian Cycles30m
4 hours to complete
Graph Classes
This week we will study three main graph classes: trees, bipartite graphs, and planar graphs. We'll define minimum spanning trees, and then develop an algorithm which finds the cheapest way to connect arbitrary cities. We'll study matchings in bipartite graphs, and see when a set of jobs can be filled by applicants. We'll also learn what planar graphs are, and see when subway stations can be connected without intersections. Stay tuned for more interactive puzzles!
4 hours to complete
11 videos (Total 55 min), 4 readings, 6 quizzes
11 videos
Trees8m
Minimum Spanning Tree6m
Job Assignment3m
Bipartite Graphs5m
Matchings3m
Hall's Theorem7m
Subway Lines1m
Planar Graphs3m
Euler's Formula4m
Applications of Euler's Formula7m
4 readings
Slides1m
Slides1m
Slides1m
Glossary10m
3 practice exercises
Trees10m
Bipartite Graphs10m
Planar Graphs10m
4 hours to complete
Graph Parameters
We'll focus on the graph parameters and related problems. First, we'll define graph colorings, and see why political maps can be colored in just four colors. Then we will see how cliques and independent sets are related in graphs. Using these notions, we'll prove Ramsey Theorem which states that in a large system, complete disorder is impossible! Finally, we'll study vertex covers, and learn how to find the minimum number of computers which control all network connections.
4 hours to complete
14 videos (Total 52 min), 5 readings, 8 quizzes
14 videos
Graph Coloring3m
Bounds on the Chromatic Number3m
Applications3m
Graph Cliques3m
Cliques and Independent Sets3m
Connections to Coloring1m
Mantel's Theorem5m
Balanced Graphs2m
Ramsey Numbers2m
Existence of Ramsey Numbers5m
Antivirus System2m
Vertex Covers3m
König's Theorem8m
5 readings
Slides1m
Slides1m
Slides1m
Slides1m
Glossary10m
4 practice exercises
Graph Coloring10m
Cliques and Independent Sets10m
Ramsey Numbers10m
Vertex Covers10m
Reviews
TOP REVIEWS FROM INTRODUCTION TO GRAPH THEORY
by SUFeb 27, 2019
Appreciate the structure and the explanations with examples. The practice tool before every lesson not makes it fun to learn but also sets the student in the context and can anticipate the concept.
by RHNov 16, 2017
Was pretty fun and gave a good intro to graph theory. Definitely felt inspired to go deeper and understood the most basic proof ideas. The later lectures can spike in difficulty though. Very nice!
by SSJun 6, 2020
Week 5 was very confusing and not well curated. Please fix this.I had to lookup youtube videos to understand the concepts and that defeats the purpose of me taking the course on coursera
by TTDec 31, 2017
This course is interesting, and it is a good introduction. I like the first four weeks' courses, while I feel the last week's course is not clear presented, which changes the instructor.
About the Introduction to Discrete Mathematics for Computer Science Specialization
Discrete Mathematics is the language of Computer Science. One needs to be fluent in it to work in many fields including data science, machine learning, and software engineering (it is not a coincidence that math puzzles are often used for interviews). We introduce you to this language through a fun try-this-before-we-explain-everything approach: first you solve many interactive puzzles that are carefully designed specifically for this online specialization, and then we explain how to solve the puzzles, and introduce important ideas along the way. We believe that this way, you will get a deeper understanding and will better appreciate the beauty of the underlying ideas (not to mention the self confidence that you gain if you invent these ideas on your own!). To bring your experience closer to IT-applications, we incorporate programming examples, problems, and projects in the specialization.
Frequently Asked Questions
When will I have access to the lectures and assignments?
Access to lectures and assignments depends on your type of enrollment. If you take a course in audit mode, you will be able to see most course materials for free. To access graded assignments and to earn a Certificate, you will need to purchase the Certificate experience, during or after your audit. If you don't see the audit option:
- The course may not offer an audit option. You can try a Free Trial instead, or apply for Financial Aid.
- The course may offer 'Full Course, No Certificate' instead. This option lets you see all course materials, submit required assessments, and get a final grade. This also means that you will not be able to purchase a Certificate experience.
What will I get if I subscribe to this Specialization?
When you enroll in the course, you get access to all of the courses in the Specialization, and you earn a certificate when you complete the work. Your electronic Certificate will be added to your Accomplishments page - from there, you can print your Certificate or add it to your LinkedIn profile. If you only want to read and view the course content, you can audit the course for free.
What is the refund policy?
If you subscribed, you get a 7-day free trial during which you can cancel at no penalty. After that, we don’t give refunds, but you can cancel your subscription at any time. See our full refund policy.
Is financial aid available?
Yes, Coursera provides financial aid to learners who cannot afford the fee. Apply for it by clicking on the Financial Aid link beneath the "Enroll" button on the left. You'll be prompted to complete an application and will be notified if you are approved. You'll need to complete this step for each course in the Specialization, including the Capstone Project. Learn more.
Will I earn university credit for completing the Course?
This Course doesn't carry university credit, but some universities may choose to accept Course Certificates for credit. Check with your institution to learn more. Online Degrees and Mastertrack™ Certificates on Coursera provide the opportunity to earn university credit.
More questions? Visit the Learner Help Center.
