Definition of a subgraph

1.1k Views Asked by At

The below two definitions come from my textbook but it doesn't give what qualifies a set $G'$ to be a subset of $G=(V,E)$.

  1. A graph is defined as a pair of sets $(V,E)$ which consists of a vertex set $V$ and an edge set $E$ .

  2. A subgraph of a graph $ G = (V,E) $ is a graph $ G'= (V',E') $ such that $E'$ is a subset of $E$, $G'$ is a subset of $G$ and all the vertices connected by the edges in $E'$ are in the subset $G'$.

If $V' \subseteq V $ and $ E' \subseteq E $ and $E' \subseteq {V'\choose2} $ , then $ G' \subseteq G $ ? Is it an if and only if condition ?

(I suspect if $G'$ should be replaced by $V'$ in definition 2. Maybe it is a typo?)

1

There are 1 best solutions below

3
On BEST ANSWER

$G'$ is a subset of $G$ is meaningless. Both are pairs of sets.

I'll assume for preciseness that in the notation $G =(V,E)$, $V$ is a set and $E$ is a subset of the set of doubletons $\binom{V}{2} = \{\{v,w\}: v,w \in V, v \neq w\}$.

If $G' = (V',E')$, a graph in its own right (so that $E' \subseteq \binom{V'}{2}$) then $G' $ is a subgraph of $G=(V,E)$ when $V' \subseteq V$ and $E' \subseteq E$). This is often written as $G' \subseteq G$ (and this is a convention, not true literally as sets, as said).

In words this just says that all vertices of $G'$ are also vertices of $G$ and all edges of $G'$ already were an edge in $G$ as well.

So yes to your question. It's an iff by definition.