Graph Theory

In this lecture we will define Graphs, Vertices, Edges, Degree of a Vertex, Degree Sequence, Graph Order, and Graph Size. And we will get to know the importance of Graphs. 

In this lecture we will get to know Subgraphs, and we will define Vertex Set and Edge Set. 

In this lecture we will explore Graph Isomorphism and its conditions. 

In this lecture we will talk about Complement Graphs, and what it means for Vertices to be adjacent.   

In this lecture we will talk about what it means for two Vertices to be connected by more than one Edge. 

In this lecture we will talk about Adjacency Matrix and Incidence Matrix.

In this lecture we will define Walks, Trails, and Paths, and the difference between them. Also, we will talk about Self Avoiding Paths (SAP). 

In this lecture we will talk about how Distance is measured in Graphs. 

In this lecture we will talk about Graph Connectedness, Cut Edge, Cut Vertex, and Separating Sets.  

In this lecture we will define Null, Trivial, Simple Graphs, Loops, and Parallel Edges.

In this lecture we will define Directed Graphs, Indegree, Outdgree, a Source, and a Sink, and we will learn how we can do Adjacency Matrix for a Directed Graph. We will also talk about Undirected, and Mixed Graphs.

In this lecture we will learn the difference between Cycle Graphs, and a Cycle in a Graph. We will also define Girth of a Graph, Path Graphs, Wheel Graphs, and Lollipop Graphs. 

In this lecture we will talk about Ladder and Prism Graphs, and how we can count the number of the Edges in each.  

In this lecture we will define Web and Signed Graphs, and we will get to know a psychologist's contribution to Graph Theory. 

The illustrations shown in this lecture are NOT owned by the instructor of this course. To reach the website containing the illustrations, follow this link : https://www.learner.org/interactives/geometry/platonic.html

In this lecture we will talk about Line Graphs which, and the process of creating them. 

In this lecture we will talk about the process of creating a Dual Graph from another Graph. 

In this lecture, we will talk about how to find the k^th Power of a Graph. 

In the lecture we will talk about the process of Joining and the steps that go into the Cartesian Product of two Graphs.  

In Cartesian Product of two graphs, I mention the word "multiply" which in this context means "Product" or "Cartesian Product".  

In this lecture we will talk about how we can create a new Graph by Union and Intersection of two Graphs. 

In this lecture we will define Vertex Coloring, Chromatic Number, k-Colorable Graphs, and Independent Sets. 

In this lecture we will define Chromatic Polynomials and show you how to use the software to find the Chromatic Polynomial of any Graph. Here is the link to Bob Weaver's website: http://www.mtholyoke.edu/~bweaver/vita/software.htm

In this lecture we will talk about Vizing's Theorem and Maximum Degree. 

In this lecture we will talk about what triggered Graph Theory. 

In this lecture we will define Euler Paths and Euler Circuits, and we will see why there isn't a solution to the Königsberg Bridge Problem. 

In this lecture we will talk about Fleury's way of finding an Euler Path or Circuit. 

In this lecture we will define Hamiltonian Paths and Circuits. 

In this lecture we will explore decomposing a Graph based on the Hamiltonian Circuits in it. 

In this lecture we will see how we can find the shortest path in a Graph using Dijkstra's Algorithm. 

In this lecture we will define Trees, their properties, their importance in Computer Science, and how we can count them using Cayley's Formula. 

In this lecture we will talk about Star Trees, Caterpillar Trees, Lobster Trees, and Banana Trees. 

In this lecture we will define Rooted Trees, Out Tree, In Tree, Parent, Child, Sibling, Ancestor, Descendant, Uncle, Leaf, Internal and External Vertices, Subtree, Levels, Height, and Depth. 

In this lecture, we will talk about different ways we can represent a Tree visually. 

In this lecture we will talk about Binary Trees, and its different types (Proper, Perfect, Complete, Infinite Complete, and Balanced Binary Trees). 

In this lecture you will learn how to convert an Algebraic or Boolean expression into a Tree and vice versa. 

In this lecture we will talk about Preorder, Inorder, Postorder, and Levelorder Tree Traversals. To practice more, go to below website and you will find numerous practice examples at the very end of the page. 

http://algoviz.org/OpenDSA/Books/OpenDSA/html/BinaryTreeTraversal.html

In this lecture we will get to know Matching, Maximum and Maximal Matching, Perfect Matching, and Near Perfect Matching. 

In this lecture, beside talking about Berge's Lemma, we will talk about Augmenting Paths, and Alternating Paths. 

In this lecture we will see the relationship between Matching and Vertex Cover for Bipartite Graphs.