1.2. 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:

1. The vertex set W of H is a subset of the vertex set V of G, meaning all the vertices of H should be the vertices of G.
2. The edge set F of H should be a subset of the edge set E of G, meaning all the edges of F should be present in E.

A subgraph is a smaller graph formed from an existing graph by taking some of its vertices and edges. To be a subgraph of another graph G:

1. Vertex Set: All the vertices in the subgraph H must also be in graph G. This means if you pick any vertex in H, it must be in G's set of vertices.
2. Edge Set: All edges in H must connect vertices that are also in H. That means every edge you include in H must exist in G, and connect vertices that are in H. This establishes that a subgraph maintains the relationships defined in the parent graph.

Consider a map of a city (graph G). If you only take a section of this map that includes some streets and intersections (subgraph H), then that section is a subgraph of the entire city map. All streets (edges) on your chosen section must connect intersections (vertices) that exist on the full city map.

A graph H will be called a proper subgraph of G if:

1. The vertex set of H is a proper subset of the vertex set of G (meaning H has fewer vertices than G).
2. The edge set of H is a proper subset of the edge set of G (meaning H has fewer edges than G). However, the original condition should not create a situation where H is equal to G.

A proper subgraph is a specific type of subgraph that is not equal to its parent graph. For it to be considered proper:

1. Vertex Set: H must not contain every vertex that G has — at least one vertex must be missing.
2. Edge Set: H must also have fewer edges than G. So it cannot have all connections that G does. Thus, it cannot include both vertices and edges in full from G, establishing a clear distinction between G and H.

Imagine you have a complete puzzle (graph G). If you take out a few pieces (vertices and edges) to form a smaller puzzle (graph H), that smaller puzzle represents a proper subgraph. If you take all the pieces out and keep the original shape, you don't have a proper subgraph anymore; you have the entire puzzle (graph G) instead.

If G = (V,E) with vertex set V and edge set E and W is a subset of vertices, then G' is called the induced subgraph or induced by the vertex set W if:

1. The vertex set of G' is W.
2. The edge set E' of G' consists of only those edges whose both endpoints are within the subset W.

An induced subgraph focuses on a specific subset of the original graph's vertices while accounting for the edges present between these vertices only. To explain:

1. Vertex Set: Only the vertices in W are included in the induced subgraph.
2. Edge Set: The edges are only those which connect vertices both in W. Any edge that connects to a vertex outside W is completely excluded, ensuring the induced subgraph captures the relationships limited to the defined vertex subset.

Consider a team of friends in a study group (graph G) where each person is connected by study topics (edges). If you choose only a few friends who share connections with each other (subgroup W), the relationships they share (such as who discusses which topics) form an induced subgraph of the larger study group. Any discussions that include friends not in the subgroup are ignored.

Several operations can be performed on graphs to create new graphs, including deleting or adding edges or vertices. The fundamental change in these operations is that:

1. Deleting an edge or multiple edges affects only the edge set without disturbing the vertex set.
2. When a vertex is deleted, all associated edges must also be removed.

Graph operations enable transformation and manipulation of graphs:

1. Edge Manipulations: When an edge is deleted, the vertices it connects remain unchanged. You simply list all existing edges except the one being deleted.
2. Vertex Manipulations: If a vertex is deleted, you must also eliminate any edges attached to that vertex, as these connections no longer exist without the vertex. These operations allow you to alter graphs for whatever analytical needs you may have.

Think of a city road map where intersections are the vertices and roads are the edges. If a road (edge) is closed, the intersections (vertices) still exist, but the connectivity changes. If you were to demolish a building (vertex) located at an intersection, any road (edge) connected to that building would also be taken off the map as that intersection would no longer be accessible.

--