(a) Mr. X claims the following:
If a relation R is both symmetric and transitive, then R is reflexive. For this, Mr. X offers the following proof.
"From xRy, using symmetry we get yRx. Now because R is transitive, xRy and yRx togethrer imply xRx. Therefore, R is reflextive."
Briefly point out the flaw in Mr. X' proof.
(b) Give an example of a relation R which is symmetric and transitive but not reflexive.
(a) Which of the following sets of edges is a cut?
$$\,\,\,\,$$(i)$$\,\,\,\,\left\{ {\left( {A,\,B} \right),\left( {E,\,F} \right),\left( {B,\,D} \right),\left( {A,\,E} \right),\left( {A,\,D} \right)} \right\}$$
$$\,\,\,\,$$(ii)$$\,\,\,\,\left\{ {\left( {B,\,D} \right),\left( {C,\,F} \right),\left( {A,\,B} \right)} \right\}$$
(b) What is the cardinality of a min-cut in this graph?
(c) Prove that if a connected undirected graph $$G$$ with $$n$$ vertices has a min-cut of cardinality $$k$$, then $$G$$ has at least $$(nk/2)$$ edges.