Is the set of edges a graph a subset of that graph?

1.1k Views Asked by At

Let $G=(V, E)$ be a non empty and undirected simple graph with its edge set $E$. Can we say that $E$ is a subset or sub graph of $G$ in any sense i.e., $E\subseteq G$ ? If so, then we can enjoy some interesting results, namely the semiring $P(E)$ is an ideal of the semiring $P(G)$ under usual union $\cup$ and intersection $\cap$ of graphs or sets, where $P(G)$ is the set of all possible sub graphs of $G$ and $P(E)$ being the set of the edges of the corresponding sub graphs in $P(G)$.

1

There are 1 best solutions below

0
On BEST ANSWER

An (ordered) pair of sets $X$ and $Y$ is denoted as $(X,Y)$. In Set Theory a pair of sets is itself a set, usually defined as $(X,Y)=\{\{X\},\{X,Y\}\}$.

However, for practical purposes we generally work with pairs as if they are objects of a different type than sets, mainly to avoid the kind of confusions in your question. Another reason is that there are other representations of pairs different than $\{\{X\},\{X,Y\}\}$ that work equally well. For example $(X,Y)=\{\{\{X\},\varnothing\},\{\{Y\}\}\}$ could be an alternative. It is therefore best not to talk about subsets of pairs of sets.

A (directed) graph is a pair of sets $(V,E)$ such that $V$ is a set (of vertices) and $E$ is a set (of edges) such that each edge $e\in E$ is a pair of sets $(v_1,v_2)$ for some distinct vertices $v_1,v_2\in V$. The graph is undirected if $(v_1,v_2)\in E$ implies $(v_2,v_1)\in E$.

As a graph is a pair of sets, it does not really make sense to talk about subsets of a graph. Therefore we define the notion of subgraphs: a subgraph of $(V,E)$ is defined as a graph $(V',E')$ such that $V'\subseteq V$ and $E'\subseteq E$ are subsets, and for each $(v_1,v_2)\in E'$ we have $v_1,v_2\in V'$.

Although a subset of a graph is generally speaking nonsensical, sometimes we abuse the notation of subsets to denote subgraphs; for graphs $G=(V,E)$ and $G'=(V',E')$ we could define that $G'\subseteq G$ is a shorthand for "$G'$ is a subgraph of $G$". In fact, this shorthand only makes sense if we regard the pair as a different type than a set, since it would otherwise be an ambiguous notation.

In a similar way we could abuse notation to define, for example, unions of graphs as $G\cup G'=(V'',E'')$ where $V''=V\cup V'$ and $E''=E\cup E'$. These are technically not really unions, but abbreviations for unions of the underlying sets of the graphs.