Definition of subgraph

982 Views Asked by At

From Rosen's Discrete Mathematics and Its Applications, 3ed, chapter 10 p. 663: subgraph

...the edge set F contains an edge in E...

Which edge is the one of interest?

...if and only if both endpoints of this edge are in W.

Why if and only if is used here? Can't they replace it with whose endpoints...? Please help. The English used here is hurting my head.

2

There are 2 best solutions below

6
On BEST ANSWER

Which edge is the one of interest?

All of them. Definition 8 says that for every single edge, the two statements "This edge is in $F$" and "This edge has both its endpoints in $W$" are equivalent statements (that's what "if and only if" is there for). In other words, for every single edge, those two statements are either both true or they are both false.

Can't they replace it with whose endpoints...?

No. The statement

The edge set $F$ contains an edge $E$ whose endpoints are in $W$.

is not the correct definition of an induced subgraph. This doesn't say that every single edge comes under the scrutiny mentioned above. It just means that there is at least one edge in $F$ that has both its endpoints in $W$. It doesn't exclude edges whose endpoints are not in $W$, and it doesn't force all edges with endpoints in $W$ to be included. Both of these things are contained in the statement using "if and only if".

2
On

You throw away vertices and reduce $V$ to $W$ and then you simultaneously reduce $E$, the original edge set to $F$ by taking all edges from $E$ that have both end points in $W$. So an edge with one end or more end points in $V\setminus W$ is thrown away and is not allowed in $F$, and all others are in $F$ (we cannot leave it out if both ends are in $W$).

In a formula: $F=\{(v,w) \in E: v \in W \land w \in W\}$

and as it is the defining property for being in the reduced edge set $F$ we can use "if and only if".

Consider extreme cases: if $W=V$, then $F=E$ and if $W=\{v\}$ then $F=\emptyset$ unless a loop at $v$ was present (and is then also in $F$) etc.