Graph Theory

Discover how graph theory began with the seven bridges of Königsberg and Euler’s 1736 paper, and explore building blocks like sub graphs, degrees, adjacency and Encinas matrices, and graphs’ definition.

Explore how graphs represent relationships by turning handshakes among five people into vertices and edges, then formalize a graph as a vertex set and an edge set with endpoints.

Explore subgraphs as smaller parts of a graph formed by subsets of vertices and edges, with subgraph vertices and edges belonging to the larger graph and sharing endpoints.

Define and compute the degree of a vertex in a graph by counting incident edges, with loops contributing two. Examine degree sequences and practice with an example graph.

Explore the sum of degrees of vertices theorem, showing that a graph’s total degree equals twice its edges, and learn about vertex degrees, order, size, and corollaries.

Explore adjacency and incidence in graphs by defining when vertices are adjacent, when edges are adjacent, and how edges are incident on endpoints, including loops.

Explore how to represent a graph using an adjacency matrix by labeling vertices, forming a square matrix, and filling entries with the number of edges between vertex pairs, including loops.

Show how to build an incidence matrix from a graph, using vertices as rows and edges as columns, marking incidences with 1 (or 2 for loops) and 0 otherwise.

Establish isomorphism by finding a vertex matching that preserves which vertices connect; two graphs with the same number of vertices and edges and the same endpoints are isomorphic.

Explore fundamental graph concepts by examining walks, paths, trails, and circuits, then study connectedness, eccentricity, diameter, and Hamiltonian paths and circuits in graph theory.

Explore walks, trails, paths, and circuits in graphs. Learn how walks alternate vertices and edges, how length and distance are defined, and how trails, paths, and simple circuits differ.

Explore how to classify sequences as walks, trails, paths, or circuits using vertex and edge repetition, with examples and edge labels from vertex one to four.

Define eccentricity as the maximum distance from a vertex; then determine the graph's diameter and radius, and identify the center and the periphery as central and peripheral vertices.

explore connectedness in graphs by studying walks between vertices, components, bridges, cut sets, separating sets, cut vertices, and how edge and vertex connectivity determine a graph’s resilience.

Explore Euler trails and circuits by analyzing vertex degrees, edges, and connected graphs, using Königsberg bridges as a case study to show when a graph has a trail or circuit.

Fleury’s algorithm finds circuits or trails by copying the graph, deleting edges in a replica, and skipping any edge whose removal disconnects the graph.

Apply Ore's theorem to certify Hamiltonicity: a simple graph with at least three vertices has adjacent-vertex degree sums at least n, making the graph Hamiltonian.

Dirac's theorem gives a sufficient condition for a simple graph to have a Hamiltonian circuit: if every vertex degree is at least half the vertices, the graph is Hamiltonian.

Solve the shortest path problem in weighted graphs using Dijkstra's algorithm to find the minimum total weight between two vertices, with city and network examples.

Explore various graph types such as simple, regular, complete, weighted, and directed graphs, learn key properties and theorems, and extend to more graph families.

Explains trivial, null, and simple graphs, defining vertices, edges, and order, and shows how to compute maximum degree n-1 and maximum edges n(n-1)/2.

Explore regular graphs where each vertex shares the same degree, and use the edges formula to test feasibility, with null, complete, cycle, and cubic graph examples.

Study complete graphs where every vertex is adjacent, cycles as two-regular Hamiltonian graphs C_n, and cubic graphs with degree three and edges E = 3n/2, including the Petersen graph.

Explore path, wheel, and platonic graphs. Path graphs are cycle graphs minus an edge; wheel graphs are cycles with a center and spokes; platonic graphs come from the five solids.

Explore bipartite graphs, defined by two disjoint vertex sets with edges only between sets, and distinguish complete bipartite graphs. Use vertex coloring and odd cycles to test bipartiteness.

Explore trees and their properties in graph theory, including spanning trees, binary expression trees, and forests, as you begin with the definition and fundamental topics.

Trees are connected graphs with no cycles, have N minus one edges, unique paths between vertices, leaves of degree one, and sum of degrees equals two times N minus two.

Explore Cayley's theorem for counting labeled trees: for n labeled vertices, there are n^{n-2} distinct trees; examples with three vertices yield three trees, and four vertices yield sixteen trees.

Design rooted trees by selecting a root, then examine level and depth, height, and how parents, children, siblings, ancestors, and descendants shape the hierarchy, including internal vertices and leaves.

Define binary trees as rooted structures with at most two children and left and right subtrees. Explore complete binary and m-ary trees, height-based vertex counts, and edge formulas.

Explore binary tree traversal methods, including level order, preorder, postorder, and in-order, and learn recursive strategies for visiting root, left, and right subtrees.

Represent arithmetic and algebraic expressions as binary expression trees by placing operators at the roots and operands at the leaves, then build and read subtrees to understand the expression.

Explore binary search trees as a data structure that organizes data for access and modification. Learn left and right subtree rules, insertion and deletion, including in order predecessor and successor.

Explore spanning trees in an undirected connected graph. Apply Kershaw's theorem to count them by building the adjacency matrix, forming a Laplacian, and calculating a cofactor.

Learn forests as disjoint unions of trees, where components are the individual trees, and edges equal vertices minus components.

Explore digraphs and tournaments, define digraphs, and examine in-degree and out-degree, isomorphism, and connectedness while introducing key concepts in graph theory.

Define directed graphs as graphs with a nonempty vertex set and an arc set of ordered pairs. Use city roads to illustrate direction, underlying graphs, simplicity, and adjacency.

Define degree in graphs: undirected degree as incident edges; in digraphs, in-degree and out-degree count arcs into and out of each vertex, with loops and sources or sinks.

Explain digraph isomorphism by matching vertices so that arcs preserve direction, mirroring undirected graph isomorphism. Identify when two digraphs are not isomorphic despite the same vertex and arc counts.

Represent directed graphs with adjacency matrix, N by N matrix of zeros and ones indicating arcs; sum columns for in-degree and rows for out-degree, noting loops and no parallel arcs.

Learn to construct the incidence matrix for a directed graph, an N by M matrix that uses 1 for away, -1 for toward, 0 otherwise, and 2 for loops.

Explore walks, paths, and cycles in digraphs, distinguishing open and closed walks, defining path and cycle, and computing length, distance, and reachable vertices.

Explore how connectedness in digraphs depends on the underlying graph and reachability between vertices, and identify strongly connected digraphs as those where every pair is mutually reachable.

Explore tournaments as digraphs where every pair of vertices is connected by one arc, representing outcomes; the degree of a vertex equals a player's score in the five-player example A–E.

Define planer graphs, introduce maximal planer graphs, and explain Euler's theorem for planer graphs to lay the foundation for this section.

Define planar graphs and plane graphs, show how K4 can be drawn without crossings while K5 and K3,3 cannot, and explain regions or faces in planarity.

Kuratowski's theorem tests planarity: a graph is planar if and only if it contains no subgraph homeomorphic to K5 or K3,3; contraction methods help identify non planar graphs.

Explore Euler's formula for a connected plane graph, linking vertices, edges, and regions with V - E + R = 2 and induction-based proofs.

Explore dual graphs in planar graphs by constructing the dual, placing vertices in each face, crossing edges to connect adjacent faces, and noting dual relationships and self-duality.

Explore fundamental graph operations by adding and deleting vertices to create new graphs, and understand how these basic actions shape graph structure.

Explore vertex deletion and edge deletion, where endpoints determine removed elements; and vertex and edge addition expanding the graph. Understand primary maintenance operations and how secondary operations arise from repetition.

Explore the cartesian product of graphs, creating a new graph from two vertex sets. Build vertices as ordered pairs and connect edges by combining edges from each factor graph.

Explore graph join and graph transpose: join connects every vertex of two graphs, creating connections between all vertices, while transpose reverses directions of all arcs in a directed graph (G^T).

Explore how to form the complement of a simple graph by flipping adjacency: edges become non-edges and vice versa, with examples of a four-vertex graph and a self-complementary five cycle.

Explore vertex coloring in graphs by assigning colors to vertices so adjacent vertices differ. Discover color classes and the chromatic number, the minimum colors for a proper coloring.

discover edge colorings, assigning colors to a graph's edges so adjacent edges differ, and learn about chi prime, color classes, and even versus odd cycles.

Apply total colorings by assigning colors to vertices and edges so that adjacent vertices and adjacent edges have different colors.

This bonus lecture thanks you for finishing graph theory and invites questions and feedback, encouraging you to revisit concepts and explore related math courses for deeper learning.