Discrete Math True or False

480 Views Asked by At

1.$\mathcal P(A\setminus B) = \mathcal P(A) \setminus P(B)$

These are power sets. False.

2.If $G$ is bipartite, then the complement of $G$ is disconnected.

False.

3.Suppose $\mathcal F$ and $\mathcal G$ are families of sets with the property that for each $A\in F$ there exists a $B\in \mathcal G$ such that $A\subseteq B$. Then $\cap \mathcal F \subseteq \cap \mathcal G$.

False

4.Let $x$ be a vertex of a connected graph $G$. Then $x$ is a cut vertex of $G$ if and only if $x$ is not a leaf of any spanning tree of $G$.

True.

1

There are 1 best solutions below

3
On BEST ANSWER

Try to have some examples in mind. I've expanded a comment out a bit.

1 - A = {1,2,3}, B = {2}, $2^{A - B}$ doesn't have $\{1,2,3\}$ which is in $P(A) - P(B)$.

2 is false - take the graph consisting of 2 vertices and no edges. The partite sets are singleton vertices (and thus, there are 2 partite sets) [ A bipartite graph is one whose vertices can be partitioned into 2 sets such that no vertices within each set are adjacent]. The complement is the complete graph on 2 vertices.

3 is false - take $G = F \cup \{ \emptyset \}$ for $\cap F \neq \emptyset$.

4 - can you provide a proof or otherwise?

5 is simple - Take $\{\{1,2\},\{3,4\},\{5,6\},\ldots\}$ and $\{\{1\},\{2\},\{3\},\ldots\}$ as subsets of $\mathbb{N}$.