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?

  • 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
    No problem. Please come back with more questions as you have them.2012-07-31