Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
6  
Where are you reading this? Does it really say "E ⊆ V (2)", or does it say "$E \subseteq V^{(2)}$"? –  Chris Eagle Jul 31 '12 at 18:50
2  
It probably says something like $V^{(2)}$. This is notation for the set of subsets of $V$ of size $2$. –  Qiaochu Yuan Jul 31 '12 at 18:51
1  
code.google.com/p/graphbook ... copy and pasting from the PDF produced my symbol, your symbol looks correct Chris. –  juwiley Jul 31 '12 at 18:54
    
$V^{2}$ or $V^{(2)}$ I guess stands for the Cartesian product $V\times V$, the set of ordered $2$-tuples (pairs) of elements from $V$. –  anon Jul 31 '12 at 18:57
    
@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.) –  Code-Guru Jul 31 '12 at 19:00
show 1 more comment

1 Answer

up vote 3 down vote accepted

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.

share|improve this answer
    
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. –  juwiley Jul 31 '12 at 19:29
    
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. –  Code-Guru Jul 31 '12 at 19:36
    
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. –  Code-Guru Jul 31 '12 at 19:38
    
Makes sense, great explanation. Thanks –  juwiley Jul 31 '12 at 20:05
    
No problem. Please come back with more questions as you have them. –  Code-Guru Jul 31 '12 at 20:10
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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