1.5. Set Theoretic Operations on Graphs

So, it turns out that since graph is nothing but a collection of two sets we can perform various set theoretic operations on a graph and obtain new graphs. So, let us discuss some of the important operations which we can perform on the graphs. So, we will first define what we call as the subgraph of a graph, if you are given a graph G = (V, E) with the vertex set being V and edge set being E. Then, a graph H = (W, F) with vertex set W and edge set F will be called as a subgraph of G, if the vertex set W of H is a subset of the vertex set V of G, namely all the vertices of H should be the vertices of G and the edge set F of H should be an edge set, there should be a subset of the edge set E of G, that means all the edges of F should be present in.

This chunk introduces the concept of subgraphs. A graph consists of a set of vertices (points) and edges (connections between points). A subgraph is a smaller graph that is formed by taking some vertices and edges from the main graph. It must meet two conditions: all vertices in the subgraph must be vertices in the main graph, and all edges in the subgraph must be edges from the main graph.

Think of a city map as a graph where intersections are the vertices, and streets are the edges. If you take a part of this map showing only certain streets and intersections, you have created a submap, or in mathematical terms a 'subgraph'.

Now let us define what we call a proper subgraph of a graph. So, we will first give an intuitive definition what exactly we can think of a proper subgraph and then we will see that definition is not correct. So, remember when we define the proper subset of a set we say that A ⊂ B, if A is a subset of B and there is something extra which is always there in B which is not there in A. So, let us try to extend that definition in the context of a proper subgraph. So, say my definition is that H graph H will be called as a proper subgraph of G if either the vertex set of H is a proper subgraph, W ⊂ V it is a proper subset of the vertex set of G and the edge set of H, F ⊂ E it is a proper subset of the edge set of G.

A proper subgraph is a special type of subgraph that is 'strictly smaller' than the original graph. For it to be proper, it needs to contain at least one fewer vertex and one fewer edge than the original graph. This means it cannot be identical to the original graph; it has to be missing something.

If we think of our city map again, a proper subgraph would be a neighborhood that does not include every street and intersection from the entire city, meaning it has fewer streets and intersections than the complete map.

So, now let us define what we call as induced subgraph. So, if you are given a graph G = (V, E) with vertex set V and edge set E and if I take a subset of vertices W, then G’ is called the induced subgraph or the induced by the vertex set W such that the vertex set of G’ is W and the edge set E’ of G’ consists of only those edges whose both the end points are within the subset W.

An induced subgraph focuses on a specific subset of vertices from the original graph. It includes all edges from the original graph that connect pairs of vertices within that subset. In other words, if we pick certain vertices, the induced subgraph will contain only the edges that connect those selected vertices directly.

Imagine your social network where each person is a vertex and friendships are edges. If you want to focus only on your close friends, the induced subgraph will show just those friends and all their direct connections (friendships) among one another.

So, now let us see some set theoretic operations that we can perform on an existing graph to get new graphs, so imagine you are given a graph then the deletion of an edge is denoted by this operation. So, imagine a small e is an edge, so if I delete an edge then the vertex set does not get disturbed, it remains the same it is only the edge set which gets affected.

When you delete an edge, the vertices it connects are still present in the graph, making the vertex set unchanged. Only the edge set is altered as the specific edge is removed. This operation helps in understanding the relationships between vertices without altering their existence.

Think of a relationship map among friends. If a specific friendship (edge) is broken between two people, they still exist; there’s just no longer a direct connection between them in terms of friendship. The overall group of friends (vertices) remains intact.

Whereas if I delete a vertex from my graph G, then definitely the vertex that gets affected and also the edge set gets affected. So, I have to remove all the edges whose one of the endpoints is v from my graph.

Removing a vertex from a graph results in the deletion of all edges associated with that vertex. This means that not only does the vertex disappear, but also any connections that it had with other vertices are lost, effectively changing the graph's structure.

Returning to our social network analogy, if a person (vertex) decides to leave the group (graph), not only do they leave, but all the friendships (edges) they had with others are also terminated, altering the dynamics of the remaining friends.

--