Graph Theory Revision

Añadido: 2026-05-09

[00:00:00]graph theory.

[00:00:03]To begin with, what is a graph? It is a set of vertices and set of edges. So, for this given graph, you can uh write the set of vertices as U, V, W, and Z. Set of edges as UV, VW, VZ, and WZ.

[00:00:29]The kind of graph we are discussing in this session The kind of graph we are discussing in this session is a simple graph.

[00:00:41]In simple graph, you have no loops and no multiple edges.

[00:00:50]Also, the nature of edge is undirected edge and there is no weight on edge. So, we are not discussing directed graph, pseudo graph, multi graph, weighted graph in this session. We are only going to discuss simple graph, which is undirected and unweighted without any loops or multiple edges.

[00:01:11]Okay, [snorts] another terminology is regarding adjacency.

[00:01:18]So, if there is an edge between U and V, you say U is adjacent to V and this this relation is symmetric, so we also say V is adjacent to U. So, in other word, you can say U and V are adjacent.

[00:01:46]There are another pair more pairs like W and Z, they are adjacent. W and V, they are adjacent. Z and W, they are adjacent. In this next next second graph, V1 V5, they are adjacent. V1 V2, they are adjacent. V2 V5, they are adjacent. V4 V5, they are adjacent and so on.

[00:02:05]The next terminology is neighborhood.

[00:02:09]So, neighbor of a vertex, suppose you consider the vertex V in the first graph, then what are the neighbor of vertex V? It is a collection of all those vertices which is adjacent to V.

[00:02:23]So, U is adjacent to V, W is adjacent to V, Z is adjacent to V. You can also consider a collection of vertices and then talk about neighbor of those subset. In other word, neighbor of, suppose you take the collection of V1 V2 and V4.

[00:02:46]Okay?

[00:02:47]So, what is this collection of all vertices which are adjacent to V2 or V2 or both? So, [snorts] what are the vertices adjacent to V2? V1 is adjacent.

[00:02:59]V3 is adjacent. V5 is adjacent. Next, V4. What are the vertices which are adjacent to V4? V1 is adjacent, already in the group, already in the set.

[00:03:08]V3 is adjacent, already in the set. V5 is adjacent, already in the set.

[00:03:15]So, this is the neighbor of the subset of vertices.

[00:03:21]Next terminology, uh next, we'll discuss the handshaking lemma. What is handshaking lemma?

[00:03:32]Handshaking lemma, it is summation of degree of the vertices, where you run the summation over the vertices, this is equal to twice the number of edges, twice the number of edges. What is degree, by the way?

[00:03:48]For example, degree of vertex U in the first graph, what it is? One. That means how many edges are attached to U? How many edges? One edges. What about degree of V? Degree of V is three. How many edges are attached to V? Three. In the second graph, what is the degree of V5?

[00:04:09]Which is equal to the number of edges attached to V5, which is four.

[00:04:15]And so on.

[00:04:16]So, we'll verify the handshaking lemma for the first graph. In the first graph, you have degree of U plus degree of V plus degree of W plus degree of Z.

[00:04:34]What is degree of U? One. Plus, what is degree of V? Three. Plus, what is degree of W? Two. Plus, what is degree of Z?

[00:04:42]Two. This is equal to eight. And how many edges do we have?

[00:04:48]How many edges do we have in the first graph?

[00:04:51]E1 E2 E3 E4, four edges. So, what is the relation between eight and four? Eight is equal to two times four. Hence, the handshaking lemma is verified for this graph.

[00:05:03]You can also verify for the uh second graph. In the second graph, what is the degree of vertex V1? Three.

[00:05:12]What is the degree of vertex V2? Three. What is the degree of vertex V3? Three. V4? Three. V5? Four. What is the sum of uh all the vertices?

[00:05:26]16.

[00:05:28]And you can count the number of edges, it must be eight.

[00:05:34]One, one, one, two, three, four, five, six, seven, eight. So, you see the number of edges are eight.

[00:05:52]And hence, the handshaking lemma is verified for the second graph.

[00:06:00]Next, we discuss path. What is a path?

[00:06:03]It is a sequence of vertices such that the corresponding corresponding uh consecutive vertices are adjacent.

[00:06:15]For example, in this case, if we write the sequence V1 V2 V3 V4 V5, then graphically, this sequence will represent V1 adjacent to V2, adjacent to V3, adjacent to V4, adjacent to V5. And it is called a path of length four. Length four means number of edges are four and we represent it by P5, that means we have considered five vertices.

[00:06:44]You can also draw P4.

[00:06:47]So, this will be like one, two, three, four. What does this mean?

[00:06:55]One is adjacent to two, two is adjacent to three, three is adjacent to four.

[00:07:00]So, it is your choice how you label it.

[00:07:04]I will give one more example with different label.

[00:07:08]Three, one, two, five, four.

[00:07:14]So, this is also a path. If it is representing a path, so what will be its pictorial representation? Three adjacent to one, adjacent to two, adjacent to five, adjacent to four.

[00:07:28]Next, cycle. What is a cycle? It is like a path whose end vertices are same.

[00:07:37]In other word, cycle of length five can be represented as V1 V2 V3 V4 V5 and you end it with V1.

[00:07:50]Graphically, you can represent it as V1 adjacent to V2, adjacent to V3, adjacent to V4, adjacent to V5, adjacent to V1.

[00:08:03]Similarly, you have a cycle of length three, this is the smallest cycle.

[00:08:09]Then you have cycle of length four.

[00:08:13]And so on.

[00:08:18]Next, tree. What is a tree?

[00:08:21]A tree is a connected graph.

[00:08:25]Connected graph and it has no cycle.

[00:08:30]What do you mean by connected graph? You pick any two vertices, there exist a path connecting the two and it has no cycle means you start from any vertices, you are not going to come back to the same vertex. This is not allowed and it is it exist for any pair of vertices. For example, a tree on two on two vertices, this is a tree. A tree on one one one vertex, a tree on three vertex, a tree on four vertex, a tree on four vertex, this is also a tree on four vertex, a tree on five vertex.

[00:09:13]This is a tree on five vertex, another tree on five vertex.

[00:09:21]Uh another tree on five vertex.

[00:09:28]Next, we can have a tree on six vertices.

[00:09:34]This is a tree on six vertices.

[00:09:37]This is also a tree on six vertices and so on. So, you see that you pick any two vertex, there exist Suppose you pick this vertex X and this vertex Y? There exist a path from this vertex you can move to this vertex, then this vertex, then this vertex. So, you see there exist a path connecting the two vertices. So, it is a connected graph. Plus, there is no cycle no cycle in me It means you begin from any vertex, you will never come back to the same vertex using a cycle or path.

[00:10:23]Okay, just a quick reminder.

[00:10:26]When you're discussing about path in a graph, when you're discussing a path in a graph, then you have to ensure that all the vertices are distinct. For example, suppose you consider this graph.

[00:10:43]Name it as 1 2 3 4 5 6. And someone ask you that write a path from 1 to 4. So, what will be the path?

[00:10:54]1 2 3 4. You see that all the vertices are distinct. Another path from 1 to 4 would can be 1 6 5 4. Another path from 1 to 4 can be 1 2 5 4. So, you see whatever path you are looking for in a graph, it must contain a sequence of distinct vertices.

[00:11:18]And that sequence must satisfy the property that consecutive terms are adjacent.

[00:11:24]Similarly, if you're looking for a cycle in the graph, similarly, for example, you're looking for a cycle that starts with two.

[00:11:33]So, this is a cycle.

[00:11:35]These are all paths.

[00:11:39]Cycles on this graph, you start with two. Two, you go to three, then go to four, then go to five, then end at two.

[00:11:46]Another cycle can be start with two, go to one, go to six, go to five, and go back to two. Another cycle can be go start with two, go to three, go to four, five, six, one, and two. So, these are all cycles. This cycle is of length four. This cycle is of length 1 2 3 4 5 6.

[00:12:08]Clear? So, in this case also, you see all the vertices are distinct except the end one because they are coming back to the same vertex.

[00:12:19]Okay.

[00:12:20]>> [clears throat] >> Complete graph.

[00:12:22]What is a complete graph? In a complete graph, all possible pair of vertices are adjacent. This is a complete graph.

[00:12:30]Uh we represent it using KN. When N is equal to one, then you get a single vertex. When N is equal to two, N equal to two means two vertices. You get two vertices, and all pair of vertices are adjacent. K3 you get the three vertices, and all pair of vertices are adjacent. So, this is your complete graph on three vertices.

[00:12:49]Similarly, K4, you take four vertices, and all pair of vertices are adjacent.

[00:12:56]Similarly, K5 you take five vertices, and you see all pair of vertices are adjacent.

[00:13:04]You can use handshaking lemma to to calculate the number of uh edges, and you can also use a combination to calculate the number of edges. So, if you use the combination, you uh what is the rule for complete graph?

[00:13:19]That all pair of vertices are adjacent.

[00:13:21]How many ways you can pick the pair of vertices? N choose two. If you use handshaking lemma, you still you will get the same value.

[00:13:33]And know that this is also a regular graph.

[00:13:37]So, what is the regularity of KN? N minus one. What is a regular graph?

[00:13:43]The number of attachment the number of edges associated with every vertex are same.

[00:13:51]And how many edges are attached with a vertex? N minus one. And how many such vertices are there? N vertices.

[00:14:03]So, this is a regular graph. This is a three regular graph. How many What is the degree of every vertex? 1 2 3 3 3 3 3 and 3. So, this is a three regular graph. This is also a three regular graph.

[00:14:25]Bipartite graph. What is a bipartite graph? You have a graph, and you are able to partition the vertices into two parts such that in each part, no pair of vertices are adjacent. And if adjacency exist, it will exist between the pair of vertices from two different parts. So, pictorially, it represents like this.

[00:14:54]For example, suppose you consider this graph.

[00:14:57]V1 V2. Is it bipartite? Yes, it is bipartite. You can put V1 in part one, V2 in part two. This is your V1. This is your V2 in part two. And this is an edge.

[00:15:11]What about this graph?

[00:15:14]V1 V2.

[00:15:16]Uh for simplicity, I will use the label 1 2 3.

[00:15:21]So, put one in first part.

[00:15:27]So, one is adjacent to two. So, two will go in the second part. Where will three go?

[00:15:33]Where will three go? It is not possible to put in part one because three should not be adjacent to one. Can you put three in part two? No, because three is adjacent to two as well. So, this is not bipartite. This is not bipartite. Let's consider one more example.

[00:15:54]1 2 3 4. Is it a bipartite graph? Let's figure out.

[00:16:01]This is your part one. This is your part two. Put vertex one without loss of generality in part one. Where will vertex two go? Two is adjacent to one, so it will go here.

[00:16:12]Where will vertex four go? Four is adjacent to one, so it cannot belong to part one. So, it must go to part two.

[00:16:20]So, is two and four adjacent? No. So, both can lie in part two. What about vertex three? Vertex three is adjacent to two, so it cannot belong to part two.

[00:16:30]Can it go to part three? Yes, it can go to part three because three is not adjacent to one. Now, you can draw the edges.

[00:16:41]So, this is your bipartite graph.

[00:16:48]Uh In general, if you talk about cycle, if it is odd cycle, then it is not bipartite.

[00:17:03]This is not bipartite.

[00:17:06]You can try to figure it out by yourself. This is part one. This is your part two. Vertex one will go here.

[00:17:12]Vertex two will go here.

[00:17:14]Vertex three will go here. Vertex four will go here. Where will vertex five go?

[00:17:18]It cannot go to part one because it is adjacent to one. It cannot go to part two because it is adjacent to four. So, in general, this is a odd cycle. It is not bipartite. There is a result given in the slides. You can read those results.

[00:17:35]Euler and Hamiltonian path.

[00:17:39]Uh it depends on which book you are studying. So, you have to be careful about the terminology used. You have a term path, then you have a term trail.

[00:17:49]Then you have a term cycle, which is treated as closed path. That means end vertices are same.

[00:17:59]In trail, uh uh in uh circuit, what is circuit? This is treated as closed trail.

[00:18:09]So, if you remember what is a path? It is a sequence of distinct vertices such that such that consecutive vertices are adjacent. What is a trail?

[00:18:21]It is also a sequence, but in this case, edges are not repeated, but vertices may be repeated. Vertices may be repeated.

[00:18:31]Uh for clarity, you can study the definition of walk. With respect to walk, you can define trail and path. So, in other word, for simplicity, for the purpose of this session, we'll look path as a sequence of vertices. We'll look trail as a sequence of edges such that edges are distinct. Vertices may be distinct or may not be. In path, vertices are distinct. So, here, for our simplicity, for this session, sequence of vertices, distinct vertices, sequence of distinct vertices such that consecutive vertices are adjacent. And for simplicity, trail is sequence of distinct edges.

[00:19:19]Vertices may be repeated in this sequence. So, in uh this given graph, can you find Hamiltonian path, Euler Eulerian trail, Hamiltonian cycle, or Eulerian circuit?

[00:19:31]What is Hamiltonian path?

[00:19:33]Hamiltonian path is a path which consist all the vertices. What is Eulerian trail? It is a trail which consist all the edges. What is Hamiltonian cycle? It is a cycle which consist all the vertices. What is Eulerian circuit? It is a circuit which consist of all the edges.

[00:19:51]So, let's begin.

[00:19:53]Looking for Hamiltonian path, you begin with one, then go here, two, then go here, three, then go here, four, then go here, five.

[00:20:03]So, this is your sequence, 1 2 3 5 4.

[00:20:11]This is a path, so you have a Hamiltonian path. If you add one more vertex, you will also get Hamiltonian cycle. So, this is your Hamiltonian path, and this one is Hamiltonian cycle. Does it also have Eulerian trail?

[00:20:31]Okay.

[00:20:31]So, you have E1, E2, E3. After E3, where will you go?

[00:20:36]You can go from five to two, E4. You can go from five to one, you can go from five to four. It is not going to help you. If you remember in the uh lecture, we have discussed that if you have Eulerian trail, this is only possible when there is only two vertices, two vertices having odd degree. Rest all the vertices must be even. This is the criteria for the existence of Eulerian trail.

[00:21:10]So, how many vertices you have of degree odd? Vertex one degree three, vertex two degree three, vertex three degree three.

[00:21:17]So, you have number you have four vertices having degree three, so it does not have Eulerian trail, and definitely does not have Eulerian circuit. For Eulerian circuit, what is what was the criteria?

[00:21:32]That all the vertices, all the vertices have even degree.

[00:21:40]Even degree, then only Eulerian circuit will exist. Now, let's look at the second uh graph. Does it have Eulerian trail or Eulerian circuit? See, the vertex one has degree four, vertex two, three, four, five all have degree two. Therefore, it does not have Eulerian trail. Eulerian trail means you cannot restart from a vertex and end at another vertex covering all the edges.

[00:22:08]But, it has Eulerian circuit. You see, you start from anywhere you wish, doesn't matter. You start from here, V3, go to V2, from V2, go to V1, from V1, go to V4, from V4, go to V5, from V5, go to V1, from V1, go go back to V3.

[00:22:32]So, this is your Eulerian circuit.

[00:22:35]Eulerian circuit.

[00:22:39]V3 V2 V1 V4 then V5, then V1, then coming back to V3.

[00:22:53]Similarly, next graph, in the third graph, can you find Eulerian trail or Eulerian circuit? You have vertex A whose degree is three. You have vertex B whose degree is three.

[00:23:06]And all the other vertices have degree even degree. E has degree two, D has degree four, C has degree four. So, it does not have Eulerian circuit, but it has Eulerian path. So, what you will do?

[00:23:20]You will start from A and end at B, or you start from B and end at A. Let's begin.

[00:23:26]You start from A, A to D, D to E, E to C, C to B, B to D, D to C, C to A, and A to B.

[00:23:47]So, all the edges are covered.

[00:23:49]So, you can write it down here.

[00:23:52]Eulerian trail A to B, B to E, E to C, C to B, B to D, D to C, C to B, uh C to A, and A to B.

[00:24:17]A D E C B D C A B.

[00:24:25]Okay.

[00:24:27]Next.

[00:24:29]This is just for exercise. You can try to figure out whether it has Hamiltonian cycle, circuit, Eulerian trail, or Eulerian circuit. Graph coloring. What is graph coloring? You have to ensure that you use the color such that no adjacent vertices are given same color. For example, if you use this two this graph, then this one can be colored red, this one can be colored black, and so on.

[00:25:04]Suppose you consider this graph, so this can be colored using yellow, this can be colored using green, this can be colored using white, and this can be colored using black.

[00:25:36]So, this is the rule you should follow while coloring the vertices. And what is chromatic number?

[00:25:44]What is chromatic number?

[00:25:46]Chromatic number is the minimum number of color required to color all the vertices. In this case, chromatic number is we represent it is by chi. Chromatic number is two.

[00:25:58]In this case, chromatic number is three.

[00:26:01]Can you color this graph using two color? No. Minimum color required to color this graph is three. Similarly, what about this graph?

[00:26:12]Chromatic number of this cyclic graph C5.

[00:26:17]You take it box, circle, box, circle, and then you cannot have neither have a box because two boxes cannot be same.

[00:26:28]Box I'm representing as color, and circle I'm representing as different color. You can neither have circle here, nor box here. So, you will require some other color here. So, the chromatic number is three.

[00:26:44]Similarly, can you find the chromatic number of this graph?

[00:26:54]So, let me label the color as 1 2 3 4 instead of the actual color. So, color one, color two, this I can give color one, this I can give color three, because I can never not neither assign it one, nor assign it as two. This I can give color as one, this I can give color as three. So, what is the chromatic number? The chromatic number is three for this graph, because three is the minimum number of color required. You cannot color it using two color.

[00:27:29]Next, we discuss graph representation.

[00:27:36]We'll only discuss adjacency matrix and incidence matrix.

[00:27:48]Incidency dence matrix.

[00:27:54]So, what is adjacency matrix?

[00:28:00]It is a n by n matrix such that the entries at I {comma} J position is equal to one if I and J are adjacent, otherwise, it is zero. Otherwise, it is zero. For example, consider this graph.

[00:28:20]Consider this graph.

[00:28:21]1 2 3 4. What you need to do? You need to find form a matrix, label the rows, label the rows, and columns in the same order with respect to vertices 1 2 3 4. You also label the column in the same order 1 2 3 4. Now, if one and one is connected, put one, otherwise zero. So, in this graph, one is we do not have loop, so definitely one and one it is not adjacent. One is adjacent to two, one is adjacent to four, one is not adjacent to three.

[00:28:57]Similarly, two is adjacent to one, two is not adjacent to two, because we do not have loop here. Two is adjacent to three, and two is not adjacent to four.

[00:29:06]Similarly, three is adjacent to not adjacent adjacent to one, adjacent to two, not adjacent to three, but adjacent to four. Similarly, four adjacent to one, not with two, adjacent to three, not with four itself. If you see it clearly, adjacency matrix is a symmetric matrix, and it has a several properties.

[00:29:35]We are not going to discuss all those.

[00:29:37]Incidence matrix. For the same graph, what will be the incidence matrix?

[00:29:42]You have to write the you have to label the rows with respect to vertices and you have to label the columns with respect to edges. So first name the edges. This is edge number one.

[00:29:56]This is edge number two. This is edge number four. This is edge number three.

[00:30:04]E1, E2, E3, E4. So it depends on the how you label the edges and vertices.

[00:30:10]Accordingly, your incidence matrix will be formed.

[00:30:15]So one is incident on E1.

[00:30:20]Yes, put it one. One is incident on E4.

[00:30:23]Yes, put it one. Remaining will be zero.

[00:30:26]Two is incident on E1. Yes.

[00:30:30]Two is incident on E2. Yes, remaining will be zero.

[00:30:34]This one will be zero. This one will be zero. Three incident on E2. Yes, this one will be zero.

[00:30:41]So you can go column wise. You can look at E3. What E3 is incident on three and four. Three and four. What E4 is incident on one and four. One and four. So you see that in every column you only have two non-zero entry. Rest all the entries will be zero, which is which is uh very clear from the geometrical representation because every edge has exactly two vertices on which it is incident on.

[00:31:12]So therefore every column has only two entries. You can answer few of the basic questions. For example, what is the degree of two?

[00:31:20]Using the adjacency matrix, look at the row two. Add all the non-zero entries. You will get two. So the degree is two.

[00:31:29]Degree of two is two.

[00:31:32]You look at the incidence matrix. Can you find the degree of two? Yes, you can find the degree of two. What is the degree of two?

[00:31:40]How many edges are adjacent with two? E1 is adjacent. E2 is adjacent. Hence two.

[00:31:47]So both graph is able to give you the questions regarding the degree of vertices.