Exercise 12.

We often define graph theory concepts using set theory. For example, given a graph \(G = (V, E)\) and a vertex \(v \in V\text{,}\) we define

\begin{equation*} N(v) = \{u \in V \st \{v,u\} \in E\}\text{.} \end{equation*}

We define \(N[v] = N(v) \cup \{v\}\text{.}\) The goal of this problem is to figure out what all this means.

  1. Let \(G\) be the graph with \(V = \{a,b,c,d,e,f\}\) and \(E = \{\{a,b\}, \{a,e\},\{b, c\}, \{b,e\}, \{c,d\}, \{c, f\}, \{d, f\}, \{e,f\}\}\text{.}\) Find \(N(a)\text{,}\) \(N[a]\text{,}\) \(N(c)\text{,}\) and \(N[c]\text{.}\)

  2. What is the largest and smallest possible values for \(|N(v)|\) and \(|N[v]|\) for the graph in part (a)? Explain.

  3. Give an example of a graph \(G = (V, E)\) (probably different than the one above) for which \(N[v] = V\) for some vertex \(v \in V\text{.}\) Is there a graph for which \(N[v] = V\) for all \(v \in V\text{?}\) Explain.

  4. Give an example of a graph \(G = (V,E)\) for which \(N(v) = \emptyset\) for some \(v \in V\text{.}\) Is there an example of such a graph for which \(N[u] = V\) for some other \(u \in V\) as well? Explain.

  5. Describe in words what \(N(v)\) and \(N[v]\) mean in general.

Hint.
in-context