Graph Theory - Complete Course on Fundamentals and Advanced Topics

What is a Graph? | Graph Theory
What are Adjacent Vertices? | Graph Theory
What is the Order of a Graph? | Graph Theory
What is the Size of a Graph? | Graph Theory
Order and Size of a Graph | Graph Theory
Empty Graph, Trivial Graph, and the Null Graph | Graph Theory
What are Adjacent Edges? | Graph Theory
What is a Subgraph? | Graph Theory
What is a Spanning Subgraph? | Graph Theory
Proper and Improper Subgraphs | Graph Theory
What is a Vertex Induced Subgraph? | Graph Theory
What is an Edge-Induced Subgraph? | Graph Theory
What is a Walk? | Graph Theory
What is a Trail? | Graph Theory
What is a Path? | Graph Theory
Proof: If There is a u-v Walk then there is a u-v Path | Every Walk Contains a Path, Graph Theory
What is a Circuit? | Graph Theory
What is a Graph Cycle? | Graph Theory, Cycles, Cyclic Graphs, Simple Cycles
Connected and Disconnected Graphs | Graph Theory
What are Connected Vertices? | Graph Theory
What are Connected Graphs? | Graph Theory
Connection as an Equivalence Relation | Graph Theory
What is a Component of a Graph? | Connected Components, Graph Theory
Explaining Components of Graphs | Graph Theory
Graphs Have at Least n-m Components | Graph Theory
Size and Degree from Vertex Deleted Subgraphs | Graph Theory
Distance, Diameter, and Geodesics | Graph Theory
Distance Between Two Vertices in Graphs | Graph Theory
What are Geodesics? | Graph Theory
Diameter of a Graph | Graph Theory
Proof: Connected Graph Contains Two Non-Cut Vertices | Graph Theory, Connected Graphs
What is a Path Graph? | Graph Theory
What are Cycle Graphs? | Graph Theory, Graph Cycles, Cyclic Graphs
What is a Complete Graph? | Graph Theory
Number of Edges in a Complete Graph (Using Combinations) | Graph Theory, Combinatorics
How Many Graphs on n Vertices? | Graph Theory
What is the Complement of a Graph? | Graph Theory, Graph Complements, Self Complementary Graphs
Proof: A Graph or its Complement Must be Connected | Graph Theory, Graph Complements
What is a Bipartite Graph? | Graph Theory
Proof: Closed Odd Walk contains Odd Cycle | Graph Theory
Proof: Bipartite Graphs have no Odd Cycles | Graph Theory, Bipartite Theorem, Proofs
Proof: If a Graph has no Odd Cycles then it is Bipartite | Graph Theory, Bipartite Theorem
How to Tell if Graph is Bipartite (by hand) | Graph Theory
What are Complete Bipartite Graphs? | Graph Theory, Bipartite Graphs
Intro to Hypercube Graphs (n-cube or k-cube graphs) | Graph Theory, Hypercube Graph
Overview of Loops in Graph Theory | Graph Loop, Multigraphs, Pseudographs
Intro to Directed Graphs | Digraph Theory
Parallel Edges in Multigraphs and Digraphs | Graph Theory, Multiple Edges, Multisets
What is the Degree of a Vertex? | Graph Theory
Neighborhood of a Vertex | Open and Closed Neighborhoods, Graph Theory
The First Theorem of Graph Theory | Graph Theory
Proof: Every Graph has an Even Number of Odd Degree Vertices | Graph Theory
Proof: Degree Sum Condition for Connected Graphs | Connected Graphs, Nonadjacent Vertices
Proof: Minimum Degree Condition for Connected Graphs | Graph Theory
What are Regular Graphs? | Graph Theory
What are Cubic Graphs? | Graph Theory
Simple Definition of Petersen Graph | Graph Theory
Degree Sequence of a Graph | Graph Theory, Graphical Sequences
Which Sequences are Graphical? (Degree Sequences and Havel-Hakimi algorithm) | Graph Theory
What are Irregular Graphs? (and why they are boring) | Graph Theory
What are Isomorphic Graphs? | Graph Isomorphism, Graph Theory
Isomorphic Graphs Have the Same Degree Sequence | Graph Theory
Graph Automorphisms and Vertex Transitive Graphs | Graph Theory
Edge Subtraction and Bridges in Graphs | Graph Theory, Edge Deletion
What are Bridges of Graphs? | Graph Theory, Edge Deletion
Proof: An Edge is a Bridge iff it Lies on No Cycles | Graph Theory
Intro to Tree Graphs | Trees in Graph Theory, Equivalent Definitions
Proof: Graph is a Tree iff Unique Paths for Each Vertex Pair | Graph Theory, Tree Graphs
Proof: Tree Graphs Have at Least Two End Vertices | Graph Theory
Proof: Tree Graph of Order n Has Size n-1 | Graph Theory
Proof: Forest Graphs have n-k Edges | Graph Theory
Proof: Connected Graph of Order n Has at least n-1 Edges | Graph Theory
Proof: Every Connected Graph has a Spanning Tree | Graph Theory
Kruskal's Algorithm for Minimum Spanning Trees (MST) | Graph Theory
Prim's Algorithm for Minimum Spanning Trees (MST) | Graph Theory
Proof on Cut Vertices Incident with Bridges | Graph Theory
Important Theorem about Cut Vertices | Graph Theory
Proof of a Characterization of Cut Vertices | Graph Theory
Proof: A Furthest Vertex is not a Cut Vertex | Graph Theory, Connected Graphs
What are Non-Separable Graphs? | Graph Theory
Vertex Cuts in Graphs (and a bit on Connectivity) | Graph Theory
Vertex Connectivity of a Graph | Graph Theory
Simple Bounds on Vertex Connectivity | Graph Theory
Vertex Connectivity of the Petersen Graph | Graph Theory
Edge Cuts and Edge Connectivity | Graph Theory
Edge Connectivity of Complete Graphs | Graph Theory
What are Vertex Separating Sets? | Graph Theory
What are Vertex Disjoint Paths? | Graph Theory
Intro to Menger's Theorem | Graph Theory, Connectivity
Proof: Menger's Theorem | Graph Theory, Connectivity
Eulerian Circuits and Eulerian Graphs | Graph Theory
Unicursal Graphs and Unicursal Lines | Semi-Eulerian Trails, Graph Theory
Proof: Graph is Eulerian iff All Vertices have Even Degree | Euler Circuits, Graph Theory
Hamiltonian Cycles, Graphs, and Paths | Hamilton Cycles, Graph Theory
Proof: Ore's Theorem for Hamiltonian Graphs | Sufficient Condition for Hamilton Graphs, Graph Theory
Proof: Necessary Component Condition for Graphs with Hamiltonian Paths | Graph Theory
Proof: Necessary Component Condition for Hamiltonian Graphs | Graph Theory
Proof: Dirac's Theorem for Hamiltonian Graphs | Hamiltonian Cycles, Graph Theory
Indegree and Outdegree in Directed Graphs | Graph Theory
In-Neighborhoods and Out-Neighborhoods in Digraphs | Graph Theory
Orientations of Graphs | Directed Graphs, Digraph Theory
What are Symmetric Digraphs? | Graph Theory
First Theorem of Directed Graphs | Digraph Theory
Underlying Graphs of Digraphs | Directed Graphs, Graph Theory
Weakly Connected Directed Graphs | Digraph Theory
Strongly Connected Directed Graphs | Graph Theory
Intro to Tournament Graphs | Graph Theory
Transitive Tournaments (Directed Graphs) | Graph Theory
Proof: Tournament is Transitive iff it has No Cycles | Graph Theory
Proof for Distances from Tournament's Maximum Outdegree Vertex | Graph Theory
Proof: Every Tournament has Hamiltonian Path | Graph Theory
Proof: Vertices of Strong Tournament Lie on Triangles | Graph Theory
Matchings, Perfect Matchings, Maximum Matchings, and More! | Graph Theory
Perfect Matchings on Complete Graphs | Graph Theory
Hall's Theorem and Condition for Bipartite Matchings | Graph Theory
Proof: Hall's Marriage Theorem for Bipartite Matchings | Graph Theory
Proof: Regular Bipartite Graph is Balanced | Graph Theory
Proof: Regular Bipartite Graph has a Perfect Matching | Graph Theory
Edge Covers and Edge Covering Numbers of Graphs | Graph Theory
Independent Vertex Sets and Independence Numbers | Graph Theory
Vertex Covers and Vertex Covering Numbers | Graph Theory
Complement of Vertex Cover is Independent Vertex Set | Graph Theory
Complement of Independent Set is Vertex Cover | Graph Theory
What are Graph Decompositions? | Graph Decomposition, Graph Theory
What are Planar Graphs? | Graph Theory
Proof: Euler's Formula for Plane Graphs | Graph Theory
Proof: Upper Bound for the Size of Planar Graphs | Graph Theory
Every Planar Graph has a Vertex of Degree 5 or Less | Graph Theory
Which Complete Graphs are Planar? | Graph Theory
Edges that Lie on One Boundary of a Region in a Plane Graph | Graph Theory
Degree of a Face in a Plane Graph | Graph Theory
Vertex Colorings and the Chromatic Number of Graphs | Graph Theory
Chromatic Number of Bipartite Graphs | Graph Theory
Chromatic Number of Complete Graphs | Graph Theory
What is a Clique? | Graph Theory, Cliques
Does Chromatic Number n Imply Clique on n Vertices? | Graph Theory
Edge Colorings and Chromatic Index of Graphs | Graph Theory
Subtracting a Vertex from a Graph (Vertex Deletion) | Graph Theory
What are Star Graphs? | Graph Theory
What is a Highly Irregular Graph? | Locally Irregular Graph, Graph Theory
Graph Representation with an Adjacency Matrix | Graph Theory, Adjaceny Matrices
What is a Maximal Clique? | Graph Theory, Cliques, Maximal Cliques
A Proof on Hamiltonian Complete Bipartite Graphs | Graph Theory, Hamiltonian Graphs
Maximum and Maximal Cliques | Graph Theory, Clique Number
Proof: Non-Regular Graph has Adjacent Vertices with Distinct Degrees | Connected Graphs
Proof: Two Longest Paths Have a Common Vertex | Graph Theory, Connected Graphs
Proof: A Graph or its Complement is not Bipartite | Graph Theory, Bipartite Graphs
Proof: Graph with all Even Degree Vertices has no Bridges | Graph Theory
Proof: Complement of Regular Non-Eulerian Graph is Eulerian | Graph Theory, Euler Graphs
Minimum and Maximum Degree Vertices in Complement Graphs | Graph Complements, Graph Theory
Bound on the Sum of Minimum Degrees of Graphs and their Complements | Graph Theory Proofs
Proof: Connected Graph with a Bridge must have a Cut Vertex | Graph Theory
Proof: Cut Vertex is not a Cut Vertex of the Complement Graph | Graph Theory
Resolving Sets and Metric Dimension of Graphs | Graph Theory
What are the Maximum and Maximal Cliques of this Graph? | Graph Theory
Bipartite Graphs with Isolated Vertices | Graph Theory, Complete Bipartite Graphs
Proof: Graph with n Vertices and n-1 Edges is a Tree | Graph Theory
Proof: A Bridge is the Unique Path connecting its End Vertices | Graph Theory
Proof: Every Edge of a Tree is a Bridge | Graph Theory
Proof: Every Graph Contains Minimum Degree Length Path | Graph Theory
Proof: Graph has a Cycle Longer than its Minimum Degree | Graph Theory
Graphs are Metric Spaces | Graph Theory
Eccentricity of a Vertex | Graph Theory
Diameter and Radius of Graphs | Graph Theory
Graph Diameter is Bounded by Radius | Graph Theory
Diameter and Radius of Tree Graphs | Graph Theory
Eccentricities of Adjacent Vertices Differ by at Most 1 | Graph Theory
Dominating Sets and Domination Number of Graphs | Graph Theory