Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

From the source of all knowledge

a graph is an ordered pair G = (V, E) comprising a set V of vertices or nodes together with a set E of edges or lines, which are 2-element subsets of V

Why must it be an ordered pair? It seems irrelevant if you mention V or E first. Must V come first since E is made up of V?

share|cite|improve this question
No, it really is irrelevant. – Karolis Juodelė Dec 14 '13 at 9:01
I've seen a lot of books define it with ordered pairs. – Celeritas Dec 14 '13 at 9:08
That's for convenience, to some extent. If I say I have a graph $(A, B)$, you know that $A$ is the vertices and $B$ is the edges. Unordered pairs are less natural. – Karolis Juodelė Dec 14 '13 at 10:14
Another thing you're missing is that the question is wrong. Graph isn't a pair. It can be described by a pair. There are plenty of other ways to describe a graph. – Karolis Juodelė Dec 14 '13 at 10:19
The question is correct, it is perfectly in order to define a graph to be an ordered pair $(V,E)$ as stated. You are free to use alternatives, but this does not invalidate the definition. – Chris Godsil Dec 14 '13 at 15:50

You don't even need a pair. A graph may be defined simply as a set $E$ of singleton or two-element sets. The set of vertices is then $V=\bigcup E.$ However, this will not do if you need to specify loops, which are edges that connect a vertex to itself, or multiple edges. Both these types of edge would be regarded as illegitimate or irrelevant in the mainstream of graph theory. And of course ordered pairs are needed to define a directed graph.

share|cite|improve this answer

Your Answer


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.