Why the definition of a subgraph is the way it is?
A graph is a pair of (V, E) where V is a set of vertices and E is a set of edges.
Alright, Alright! We all have read the definition of a graph at some point of time in our lives. And the definition goes like this: “A graph is a pair of (V, E) where V is a set of vertices and E is a set of edges.” But what does it mean in easy terms?
Consider the graph shown below:
The graph consists of five vertices: V = {1, 2, 3, 4, 5}. What would happen if we formed a relation on V. Which is a cross product on set V: (V x V)
Out of all the pairs of vertices in V x V, what if we chose only those pairs which are linked in the graph shown above?. Pairs like (1, 2), (2, 3), (3, 4), (4, 5) and (5, 1)are linked in the graph shown above. (1, 2) and (2, 1) mean the same since the graph is undirected.
Let’s carve out the linked pairs (1, 2), (2, 3), (3, 4), (4, 5) and (5, 1) from the set of V x V. Are not these linked pairs reflecting the edges of our graph. Let’s store the carved out linked pairs in a set called E.
E = {(1, 2), (2, 3), (3, 4), (4, 5), (5, 1)}
A graph is built upon V and a subset of V x V. Edges of the graph are a small chunk of subset V x V. Thus, a graph basically is all about vertices (V). The wikipedia defines the set of edges E as:
E ⊆ {(x,y) | (x,y) ∈ V x V} Edges are derived bits of vertices (relation on vertices). I personally prefer to understand there is nothing called edges in a graph. Edges are simply (chunks of) V x V in disguise. Vertices are the creator of the graph. Vertices are the whole and sole of graph. Edges are illusionary entities.
Now, moving to the subgraph part. According to the dictionary of Algorithms and Data Structures by Paul E. Black
A graph G'=(V', E') is a subgraph of another graph G=(V, E) iff
V'⊆ V and
E'⊆ E ∧ ((v1, v2) ∈ E' → v1, v2 ∈ V').Simply said:
Graph G is equivalent to (V, E). Then subgraph G' is equivalent to (V', E') where V' is subset of V
E' is subset of E but
for each edge (e) in E': end points of edge e must exist in V'
Consider the graph and its subgraph shown above. Graph G is equivalent to (V, E). Subgraph G’ is equivalent to (V’ , E’) where V’ is subset of V and E’ is subset of E. Most importantly for each edge “e” in E’ {e2, e3} end points of e exist in V’.
Why does the subgraph make it compulsory for each edge “e” in E’ to have its endpoints in V’?
Let’s try to violate this property. Let’s try to carve out a subgraph from a graph as shown below:
Here, end points of edge e3 (3, 4) do not fall in vertex V’. Remember we discussed in this blog, edges are derived out of vertices (V x V). So if perform cross product on V’
V' x V' = { (1, 1), (1, 2), (1, 3),
(2, 1), (2, 2), (2, 3),
(3, 1), (3, 2), (3, 3)
}The linked pair of (3, 4) does not ever get formed. Hence edge e3 must not exist in the sub graph. The subgraph is pseudo and illegitimate.
Inserting an edge without its end vertices is like constructing a house without pillars:
Hence, it is mandatory for each edge “e” in E’ to have its end points in V’. This property is equally important to other two properties of the subgraph. (V’, E’ is subset of V, E).
Hence, the definition of a subgraph is the way it is and it must be followed at all costs.
