Introduction Class + Graph Theory

Lecture 1

Introduction Class + Graph Theory

Link to the Classroom Lecture

Graphs

We introduced the idea of Graphs.

.

Handshaking Lemma

We spoke about handshakes in the classroom and how we can model it using Graphs.

By degree, we mean the number of lines that are adjacent on a point, or simply speaking, the number of friends that a person keeps

Isomorphic Graphs

We saw how two graphs that are appearingly different can actually be the same.

1. Quiz: Are the following two graphs the same?
   

2. Test: Are the following two graphs the same?
   

3. Quiz: Understand how the graphs as illustrated in the lecture (link), are not isomorphic. Why? Google for Petersen Graph for some fun reading.

4. Test: If you are given two graphs on 100 nodes, how can one write a piece of code to find out if these two graphs are the same or not? What is the complexity involved in finding this out?