What is the meaning of the square brackets in theorem 8.6.30 (Introduction to Graph Theory) book?

73 Views Asked by At

In the book (Introduction to Graph Theory) by Douglas West , what is the meaning of the square brackets in $|[ S , \overline{S} ]|$ ?

WHAT NOTATION

1

There are 1 best solutions below

0
On

That text book has the Answer on Page 152 :

"Given $S , T \subset V(G)$ , we write $[S , T]$ for the Set of Edges having one End-Point in $S$ and the other in $T$.
An Edge Cut is an Edge Set of the form $[S , \overline{S}]$ , where $S$ is a Non-Empty Proper Sub-Set of $V(G)$ and $\overline{S}$ denotes $V(G) - S$."

Concisely , the Author later states that "It is the set of edges joining a vertex in $S$ to a vertex not in $S$" , which is very Intuitive.

More-over , it is standard convention / notation to use $|A|$ to indicate Size of Set $A$.

Hence , $|[S , \overline{S}]|$ indicates "the Size of the Edge Cut" , while that theorem is giving a lower Bound on this Size.

Here is that Page with more Detail :

EDGE CUT