2
$\begingroup$

I'm trying to learn more about graph theory, but I'm getting confused by the initial definition:

"A graph $G = (V, E)$ is an ordered pair of finite sets. Elements of V are called vertices or nodes, and elements of $E \subseteq V^{(2)}$ are called edges or arcs. We refer to V as the vertex set of G, with E being the edge set."

I interpret this as "elements E in the subset of V are called edges". This seems to conflict with the next sentence, which defines a graph as being edges and vertices...i.e.two separate sets of things? It doesn't make intuitive sense for edges to be a kind of vertex. Whats the correct interpretation of this?

  • 6
    Where are you reading this? Does it really say "E ⊆ V (2)", or does it say "$E \subseteq V^{(2)}$"?2012-07-31
  • 2
    It probably says something like $V^{(2)}$. This is notation for the set of subsets of $V$ of size $2$.2012-07-31
  • 1
    https://code.google.com/p/graphbook/ ... copy and pasting from the PDF produced my symbol, your symbol looks correct Chris.2012-07-31
  • 0
    $V^{2}$ or $V^{(2)}$ I guess stands for the [Cartesian product](http://en.wikipedia.org/wiki/Cartesian_product) $V\times V$, the set of ordered $2$-tuples (pairs) of elements from $V$.2012-07-31
  • 0
    @anon Usually the edge set is a set of *un*ordered pairs, rather than ordered ones. (Unless of course, you study digraphs. And then they are called arcs, not edges.)2012-07-31
  • 0
    @Code-Guru Woops, yes. $V^2$ would be ordered, $V^{(2)}$ unordered, that makes sense.2012-07-31

1 Answers 1

3

If you look at the bottom of page 2 of your text, you will see the following explanation:

Notation If $S$ is a set, let $S^{(n)}$ denote the set of unordered $n$-tuples (with possible repetition). We shall sometimes refer to an unordered $n$-tuple as an $n$-set.

Now when the text later says "$E \subseteq V^{(2)}$." This means that $E$ is a set of unordered 2-tuples (or pairs) of vertices.

With that detail out of the way, I strongly suggest that you try to get an intuitive idea of what graphs are. Generally we represent graphs as "connect-the-dot" drawings. The vertices are drawn as dots and the an edge is drawn as a line (or curve) connecting the two dots. With this kind of picture in mind, we can now make sense of the precise definition of an edge: an edge is defined by the two vertices it connects.

I hope that you take the time to study the diagrams of example graphs in your textbook as they will make the above description clearer.

  • 0
    So an edge is defined by a 2-tuple of vertices. That makes some sense, but in diagrams edges are referenced as 'e1', etc. Since edges can have a direction (and I assume) other properties, I wonder why the formal definition only refers to them in terms of the vertices they connect, instead of as distinct entities different from vertices.2012-07-31
  • 0
    In graph theory, usually undirected graphs are introduced first. This means that the edges do not have any direction. You will probably learn about directed graphs, or digraphs, later. Also, pairs of vertices are certainly distinct entities from individual vertices. We see a similar thing when graphing points in algebra and geometry: the point P given by the coordinates (x, y) is not the same thing as the real numbers x or y. Note the other similarity here: the point itself can be given a name independent from the names of the coordinates.2012-07-31
  • 0
    If the edge $e_1$ connects vertices $v_1$ and $v_2$, then we can write $e_1=\{v_1, v_2\}$ and use either side of this equation to "name" the edge.2012-07-31
  • 0
    Makes sense, great explanation. Thanks2012-07-31
  • 0
    No problem. Please come back with more questions as you have them.2012-07-31