How to prove that a graph A is a subgraph of graph B?

2.5k Views Asked by At

From the definition of a subgraph:

A graph whose vertices and edges are subsets of another graph.

Source: https://xlinux.nist.gov/dads/HTML/subgraph.html

However, I am not able to apply it on the actual graphs.

Suppose I have 2 graphs (please see the images), how to prove that the graph B is the subgraph of graph A.

1

There are 1 best solutions below

2
On BEST ANSWER

Let us begin by choosing a labeling of the graphs in question

enter image description here

enter image description here

Now... these images are merely graphical pictoral representations of the actual underlying mathematical objects being discussed. Recall that a graph is technically a pair of sets $G = (V,E)$ where $V$ is the set of vertices and $E$ the set of edges, recalling that $E$ is a subset of $V\times V$.

Writing out these graphs in terms of the sets they represent we have:

$$B = (\{\color{blue}{1,2,3,4}\},\{\color{red}{\{1,4\},\{2,3\},\{3,4\}}\})$$

and

$$A = (\{\color{blue}{1,2,3,4},5\},\{\{1,2\},\color{red}{\{1,4\},\{2,3\}},\{2,4\},\color{red}{\{3,4\}},\{4,5\}\})$$

From here, it is clear to see that $\{\color{blue}{1,2,3,4}\}\subseteq \{\color{blue}{1,2,3,4},5\}$ so the vertex set of $B$ is indeed a subset of the vertex set of $A$ as well as $\{\color{red}{\{1,4\},\{2,3\},\{3,4\}}\}\subseteq \{\{1,2\},\color{red}{\{1,4\},\{2,3\}},\{2,4\},\color{red}{\{3,4\}},\{4,5\}\}$ so the edge set of $B$ is a subset of the edge set of $A$. This, following from the basic definitions of what it means to be a subset of. $X$ is considered a subset of $Y$ iff every element of $X$ (if any exist in the first place) is also an element of $Y$.

If the labelings of the graphs were different, we could be in a situation where officially the one would not be a subgraph of the other. It could however be isomorphic to a subgraph of the other. To be isomorphic to a subgraph of the other, that just means that there is a way to relabel the vertices and edges in such a way as to make it an actual subgraph of the other. Since you appear to be working with unlabeled graphs, it is not uncommon to drop the "isomorphic to" aspect of the phrase since this is the only possible interpretation, effectively requiring you to choose a labeling of both graphs before continuing.

I will point out that the task of actually finding a relabeling of the edges and vertices such that the one graph is a subgraph of the other is a "difficult" problem (Specifically, it is a NP-complete problem). It is possible that one choice of labels don't work but a different choice of labels would have worked. In our specific case, there was a clear choice of labels to use since the images used for the two graphs were so similar. In the generalized problem it might not be clear at all.

For techniques, algorithms, and more information on the fully generalized problem, see Subgraph isomorphism problem on wikipedia.