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
We define \(N[v] = N(v) \cup \{v\}\text{.}\) The goal of this problem is to figure out what all this means.
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{.}\)
What is the largest and smallest possible values for \(|N(v)|\) and \(|N[v]|\) for the graph in part (a)? Explain.
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.
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.
Describe in words what \(N(v)\) and \(N[v]\) mean in general.