1.1. Various Operations on 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 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 a subset of the edge set E of G.

A subgraph is a smaller graph formed from a larger graph. In this case, you have graph G with vertices V and edges E. For another graph H to be a subgraph of G, it must use some of the same vertices from G (its vertex set W must be from V) and its edges must connect those vertices exactly as they are in G (the edge set F must be part of E). This means H can only contain edges that correspond to the vertices it has taken from G.

Think of a subgraph like a subset of a group of friends. If you have a group of friends (graph G) with a certain number of connections (edges), a smaller group of just a few friends (graph H) can only include friends from the larger group and their connections can only be those that exist in the larger group.

The right definition of the proper subgraph is the following: H is a proper subgraph of graph G if it is a subgraph of G and it is a subgraph which is different from the graph G or the parent graph.

A proper subgraph is simply a subgraph that isn't exactly the same as the original graph G. This means it has fewer vertices or fewer edges than G. It must be a subgraph first, so it contains some but not all vertices or edges from G, ensuring that it can be distinguished from G. If H is just G with some edges or vertices removed, then it is a proper subgraph.

Imagine a pizza (graph G) and you take a slice off it (graph H). The slice is a representation of the entire pizza but is not the whole pizza. This slice still has the same ingredients (vertices) but is simply a smaller version of the whole pizza.

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 endpoints are within the subset W.

An induced subgraph is formed by taking a specific set of vertices from the original graph and including all the edges that connect them. If you have a graph G and decide to focus on a subset of vertices W from G, the induced subgraph G' will consist of just those vertices and the edges that connect them in the original graph. No other edges that include vertices outside of W will be considered.

If G is a city with roads (edges) connecting various landmarks (vertices), and you pick a few landmarks (subset W), your induced subgraph would be just those landmarks and only the roads that connect them without considering any roads leading to places outside this selected group.

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. On the other hand, if I delete a vertex from my graph G, then definitely the vertex that gets affected and also the edge set gets affected.

When you delete an edge from a graph, you're simply removing the connection between two vertices that remains in the graph. However, when a vertex is deleted, you not only lose the vertex itself but also all the edges connected to that vertex, as they no longer have one of their endpoints. Thus, the overall structure of the graph changes more significantly when vertices are removed compared to deleting edges.

Consider a network of friends where each friend represents a vertex and the connections (friendships) between them are the edges. If one friend (vertex) decides to end a friendship (delete an edge), the rest of the friendships stay intact. But if that friend leaves the group altogether (delete the vertex), they take away all their friendships with them, changing the dynamic of the entire group.

Now let us discuss the various data structures that we can use to represent graphs. We have what we call as the adjacency matrix representation, a boolean matrix.

Graphs can be represented in several ways, the most common being adjacency matrices and adjacency lists. An adjacency matrix is a 2D array where each cell indicates whether two vertices are connected by an edge. If the graph is dense (many connections), this representation is useful. However, in sparse graphs (fewer edges), an adjacency list may be more effective. An adjacency list stores all neighbors for each vertex, saving space as it only includes existing edges.

Imagine the adjacency matrix as a detailed table with every possible friendship detailed, checking if every person knows every other person (1 for yes, 0 for no). On the other hand, the adjacency list is more like a phone book, where each person only lists their actual friends, contacting only those with whom they share a connection, thereby being more efficient in its representation.

If you see these two graphs, pictorially they are drawn in a different way. However, structurally they are similar graphs. What do I mean by structurally they are similar graphs?

Graph isomorphism indicates a structural similarity between two graphs. Even if two graphs look different (different layouts or labels), they are considered the same if there exists a way to map their vertices such that the edges remain unchanged. This mapping shows that the two graphs encode the same information despite appearances, making them isomorphic.

Think of different languages using the same universal expressions. For instance, two people might speak different languages but can convey the same message through equivalent phrases. Similarly, graph isomorphism reflects that different drawings may represent the same underlying connections.

An undirected graph is called connected if there exists a path between every pair of distinct vertices. What is the connected component of a graph? A connected component of a graph is the maximal connected subgraph of the graph.

A graph is connected if you can find a path between any two vertices. If this is true for all vertices, there’s only one connected component, which is the whole graph. However, if there are some vertices that cannot reach others by any path, we call each separate piece a connected component. Each component is maximally connected, meaning it cannot be extended further with other vertices and edges without losing its property of being a separate component.

Think of a graph like a network of islands. If each island can reach every other island by bridges (connections), the whole network is connected. However, if you have some isolated islands that cannot reach any other islands, each isolated island or cluster of islands becomes a connected component.

--