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.

Offered By

## Introduction to Graph Theory

University of California San Diego## About this Course

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

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

**6 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!

**6 hours to complete**

**3 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!

**3 hours to complete**

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

## Reviews

- 5 stars66.40%
- 4 stars23.21%
- 3 stars7.03%
- 2 stars2.23%
- 1 star1.11%

### TOP REVIEWS FROM INTRODUCTION TO GRAPH THEORY

Very friendly and applied course.

A well-balanced approach, even layman can understand the concept with exceptional ease.

Though it is beginner level course some concepts are hard to grasp. Gives perfect introduction in graph theory. Useful for computer science subjects.

This course is really good. If someone has interest in graph theory or he wants to learn it, then this course is definitely a good start.

I just audit this course and it's very good. It gives basic ideas about graph theory and this is a super interesting subject!

## Frequently Asked Questions

When will I have access to the lectures and assignments?

What will I get if I purchase the Certificate?

Is financial aid available?

More questions? Visit the Learner Help Center.