Graph Theory

MATH X 451.47

This course, the second of a two-quarter sequence in combinatorial methods, deals with the history, theory, and applications of this most intriguing and useful mathematical discipline.

READ MORE ABOUT THIS COURSE

What you can learn.

  • Discuss planar graphs, Kuratowski’s Theorem, and isomorphism
  • Visualize how dual graphs align with Euler’s formula
  • Classical applications of the theories Three-Utility Problem, Marriage Problem, and the Four-Color Theorem
  • Explore Hamiltonian paths, tress, adjacency and incidence matrices

About this course:

A graph consists of a finite set of vertices and a finite set of edges, each edge being identified with an unordered pair of vertices. The study of such structures dates back to Euler’s 1736 paper on the Königsberg Bridge Problem, the first of many “practical” applications for which graph theory has both supplied insights and raised questions. This course, the second of a two-quarter sequence in combinatorial methods, deals with the history, theory, and applications of this most intriguing and useful mathematical discipline.  Topics to be discussed include planar graphs (including Kuratowski’s Theorem), isomorphism, dual graphs, Euler’s formula, complete graphs, connectedness, Euler and Hamiltonian paths, tress, adjacency and incidence matrices, and coloring problems.  Classical applications of the theory—including the famous Three-Utility Problem, Marriage Problem, and the Four-Color Theorem—will complement the development of the theory.
Prerequisites
Calculus and some exposure to advanced mathematical methods.

Contact Us

Speak to a program representative. Hours: Mon-Fri, 8am-5pm
Keep up to date on the latest news and offerings in Math & Statistics

vector icon of building

Corporate Education

Learn how we can help your organization meet its professional development goals and corporate training needs.

Learn More

vector icon of building

Donate to UCLA Extension

Support our many efforts to reach communities in need.

Innovation Programs

Student Scholarships

Coding Boot Camp

Lifelong Learning