Elementary Foundations: An introduction to topics in discrete mathematics

Suppose $U$ is a universal set, and consider $\mathcal{P}(U)$ partially ordered by $\subseteq$ as usual. In the full set $\mathcal{P}(U)\text{,}$ the unique maximum element is $U\text{,}$ which is just another way of saying that every element of $\mathcal{P}(U)$ is a subset of $U\text{.}$ And the unique minimum element is $\varnothing \text{,}$ which is just another way of saying that the empty set is a subset of every subset of $U\text{.}$

Now consider a subset $\mathcal{A}\subseteq \mathcal{P}(U)\text{,}$ so that $\mathcal{A}$ is a collection of subsets of $U\text{.}$ Because of the existence of maximum and minimum elements, these elements also serve as an upper and lower bound, respectively, for $\mathcal{A}\text{.}$ However, one can also find a least upper bound for $\mathcal{A}$ by taking the union of all the subsets of $U$ contained in $\mathcal{A}\text{,}$ and one can find a greatest lower bound by taking the intersection of all the subsets of $U$ contained in $\mathcal{A}\text{.}$

Consider the graph $G$ in Figure 19.5.8.

Let $\mathcal{S}(G)$ represent the collection of subgraphs of $G\text{,}$ partially ordered by the subgraph relation. (By my count, $|\mathcal{S}(G)|=110\text{.}$) Let $\mathcal{C}(G)$ represent the collection of connected subgraphs of $G\text{.}$ (By my count, $|\mathcal{C}(G)|=15\text{.}$) A maximal elements of $\mathcal{C}(G)$ would have to be a connected subgraph of $G$ that is contained in no larger connected subgraph of $G$ — but this is precisely the definition of connected component. Hence $\mathcal{C}(G)$ has three maximal elements, the three connected components you see in Figure 19.5.8. However, a maximum element of $\mathcal{C}(G)$ would be a connected subgraph of $G$ which contains every other connected subgraph of $G\text{,}$ and the existence of multiple connected components in this example non-connected graph makes such a subgraph impossible.