1.3. Proper Subgraph

So, let us define what we call a proper subgraph of a graph. So, say my definition is that H graph H will be called a proper subgraph of G if either the vertex set of H is a proper subset of the vertex set of G and the edge set of H is a proper subset of the edge set of G.

A proper subgraph is a type of subgraph where it contains some, but not all, vertices and edges from the parent graph. To be considered a proper subgraph, the vertex set of H (denoted by W) must be a proper subset of the vertex set of G (denoted by V), meaning that W should contain fewer vertices than V. Similarly, the edge set of H (denoted by F) must also be a proper subset of the edge set of G (denoted by E), indicating that H must have fewer edges than G. If either condition is not met, then H is not considered a proper subgraph.

Think of a proper subgraph like a team within a larger sports organization. If the whole organization includes players from multiple teams, a specific team is like the proper subgraph—it has fewer members than the entire organization (parent graph) and may also have fewer games (edges) than the total games the organization is involved in.

But this is my definition, then with respect to this definition if I take my graph G and H to be this then H will not be considered as a proper subset of G. This is because all the vertices of H are the vertices of G as well.

In this part, the speaker realizes that the initial definition of a proper subgraph is insufficient because it does not encompass situations where a graph H can still contain all vertices of G and yet not be proper. For H to be considered proper, there must be exclusive elements in G that are unavailable in H. The example given demonstrates a scenario where if H has no extra vertices (it only mirrors vertices from G), then H fails to qualify as a proper subgraph even if it follows the rules proposed initially.

Imagine you have a box full of 10 different colored markers. If you take out 9 markers of the same colors and rearrange them in a neat line (still using all the colors from the box), the line you created does not represent a proper subset because it consists entirely of the original markers. To be a proper subset, it needs at least one distinct color that was not included.

So that is why the right definition of the proper subgraph is the following. I will say that 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.

The correct understanding of a proper subgraph requires two key criteria: First, graph H must qualify as a subgraph of graph G. This means it meets the initial requirements of having vertex and edge sets that are subsets of those in G. Second, graph H must not be the same as G itself; they must differ in some aspects. This ensures that H has fewer vertices or edges than G, thus establishing it as a proper subgraph.

Returning to our sports team analogy, think of H as a youth soccer team that consists of players who practice together and play matches together, which also forms part of a larger organization. The youth team cannot have every single player from the entire organization, or else it wouldn't be a distinct entity but rather the whole organization itself!

--