The number of binary strings of $$n$$ zeros and $$k$$ ones such that no two ones are adjacent is:

(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.

Two girls have picked 10 roses, 15 sunflowers and 14 daffodils. What is the number of ways they can divide the flowers among themselves?

Let $$G$$ be a connected, undirected graph. A $$cut$$ in $$G$$ is a set of edges whose removal results in $$G$$ being broken into two or more components which are not connected with each other. The size of a cut is called its $$cardinality$$. A $$min-cut$$ of $$G$$ is a cut in $$G$$ of minimum cardinality. Consider the following graph.

(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.