I'm just starting to learn graph theory. I have two questions about notation:

1). For a graph $G$ we denote the vertex set $V$ and the edge set $E$ by $G=(V,E)$.
So we have a graph $G=$ ({$v_{1},v_{2},...,v_n$}, {$e_{1}e_{2},...e_{n}$}).
My textbook presents the edge set as $E=${($v_1,v_2$), ($v_1,v_3$),...,($v_i,v_n$)}.
If I remember correctly, set theory rules tell us that ( ) are used to indicate order, and { } are used when the order doesn't matter. Why are ( ) used in this case when denoting the vertices in the edge set?

2). I'm used to seeing this formula, $E\subseteq V\times V$, to indicate a relation on $V$ denoting the elements of $E\subseteq V\times V$ as edges. In another set of notes that I stumbled upon, this notation is used: $E\subseteq V\bigotimes V$ as edges. What is the $\bigotimes$, I'm confused about that.


  • 1
    $\begingroup$ Perhaps this is a directed graph, where an edge has a direction? Another notation I have seen is $[V]^2$ which the set of all two element subsets of $V$. $\endgroup$ – copper.hat Jun 28 '13 at 6:24

Order of vertices in an edge is important if we consider directed edges. The notation as pairs of vertices (which does not allow multiple edges, by the way!) fits well with viewing $E$ as subset of $V\times V$. The notation $\otimes$ is rather known from linear algebra where it denoites the tensor product, while here it apparently stands for the set of unordered pairs ov elements of $V$ (as needed for undirected graphs). Cf. also the notations $V^2$ for $V\times V$ versus $[V]^2$ for $V\otimes V$.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.