Let say I have a graph $\mathcal{G}$. Denote this graph by $\mathcal{G}=(\mathcal{V}, \mathcal{E})$ where $\mathcal{V}$ is the set of vertices and $\mathcal{E}$ is the set of edges.
My question is simple and very basic (it could be wrong): Can I say that the graph $\mathcal{G}$ is represented by $\mathcal{G}=(\mathcal{V}, \mathcal{N})$ where $\mathcal{N}\subseteq \mathcal{V}\times \mathcal{V}\,$? For a complete graph, $\mathcal{N}= \mathcal{V}\times \mathcal{V}\,$? Or this notation is wrong? When to use this notation?
$\endgroup$ 22 Answers
$\begingroup$As others have mentioned, the cartesian product would include both $(u,v)$ and $(v,u)$, which is not desirable for an undirected graph. The cartesian product also includes $(v,v)$, which is not desirable for simple graphs. For a simple undirected graph with vertex set $\cal V$ and edge set $\cal E$, you could instead define $\cal E$ as a subset of $\binom{\cal V}{2}$, where $\binom{\cal V}{2}$ is the set of all subsets of $\cal V$ of size 2. So a definition of the complete graph would be:
$$K_n = \left(\cal V, \binom{\cal V}{2}\right) \textrm{, where } |\cal V| = n$$
$\endgroup$ $\begingroup$In a directed graph, the Cartesian product notation is spot on. However, in an undirected graph, I don't like it. It indicates $(v_{1}, v_{2}) \neq (v_{2}, v_{1})$. Of course, notationally, we can wave our hands based on context.
I prefer $E = \{ (v_{1}, v_{2}) : v_{1}, v_{2} \in V, v_{1} \neq v_{2} \}$. This also takes care of the diagonal entries, as we can't have loops in a simple graph. It also alleviates the directional implication from the Cartesian product notation.
$\endgroup$
