Meaning of V \cup E for a Graph

Question

Given a Graph G = (V,E), where $V \in {1,2,..,n}$ and E is the corresponding element of the edge set. Does $V \cup E$ mean anything (the reason being edge is defined with respect to two nodes)?

Answer 1

To paraphrase a relevant xkcd:

If you ever find yourself taking the union $V \cup E$, set down the marker and back away from the whiteboard; something has gone horribly wrong.

Whenever we have two sets, such as $V$ and $E$, we can consider their union $V \cup E$; but just because we can, doesn't mean we should. There are a couple of good reasons not to:

---

First of all, the result depends on your formalization of graphs. There are several:

• Some people take $E$ to be a subset of $\binom V2$, so that an edge is a $2$-element subset of $V$.
• But you will have a bad time with this definition if your graph has loops, so some people take $E$ to be a subset of $V \times V$ and just ignore the order of the ordered pairs.
• Finally, some people just say that $E$ is an arbitrary set, and there is an incidence relation on $V \times E$ that tells us when a vertex is the endpoint of an edge.

Why this matters is that in each case, we might define $V$ to have some of those same elements. For example, if we use the first definition, then maybe $V$ consists of the vertices $1$, $2$, and $\{1,2\}$. If $E$ only includes an edge from $1$ to $2$, that will be represented as $\{1,2\}$, so we'll have $V \cup E = V$. But if we use the ordered-pair definition, then that edge will be $(1,2)$ instead, and $V \cup E = \{1, 2, \{1,2\}, (1,2)\}$.

Philosophically, what we do with graphs shouldn't depend on the specifics of the definition of a graph. If it does, then we should do things differently.

---

Second, even if we specify which formulation we use, the result is not a graph-theoretic property: isomorphic graphs don't necessarily have "isomorphic" (that is, same-cardinality) unions $V\cup E$.

If we take the example from before, the graph with vertices $1,2,\{1,2\}$ and edge $\{1,2\}$ is isomorphic to the graph with vertices $1,2,3$ and edge $\{1,2\}$. But $V\cup E$ has size $3$ in the first case and size $4$ in the second.

---

Finally, if you take a disjoint union, these problems are avoided and the result is occasionally even useful. By a disjoint union here, I mean the set (denoted $V \amalg E$ or $V \mathbin{\dot{\cup}} E$) defined in some way such as $$ V \mathbin{\dot{\cup}} E = (\{0\} \times V) \cup (\{1\} \times E) $$ which makes sure to keep vertices and edges separate. We identify $\{0\} \times V$ with $V$ and $\{1\} \times E$ with $E$, so that we think of elements of $ V \mathbin{\dot{\cup}} E$ as being elements of $V$ or of $E$: but never both at once!

One place where this comes up is the notion of a total coloring of a graph, which is a function $$ f: V \mathbin{\dot\cup} E \to C $$ for some color set $C$, such that adjacent or incident elements of $V \mathbin{\dot{\cup}} E$ receive different colors.

But here, $V \mathbin{\dot\cup} E$ is just a way to say "we are talking about the vertices and edges at the same time". It doesn't tell us anything interesting on its own.