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

Background: In this a graph is G=(V,E) where V is the set of all vertices and E is a set of 2-element subsets of V. For example: G=({1,2,3,4},{{1,2},{1,3},{2,4}}). E stands for edges similar to a line segment between point A and point B such that it is represented by {A,B}. {A,A} is not an acceptable edge. For antisymmetric, the following must be true: If x~y and y~x, then x=y. For transitive, the following must be true: If x~y and y~z, then x~z.

Question 1: Construct a graph G for which the is-adjacent-to relation, ~, is antisymmetric.

Question 2: Construct a graph G for which the is-adjacent-to relation, ~, is transitive.

share|cite|improve this question
up vote 1 down vote accepted

I assume your edges are directed, or else these questions are impossible. One example that works for both questions is to take a (partial) ordering on some set (the usual ordering on a finite set of integers will work just fine). Let $\{a,b\}$ be an edge if and only if $a<b$. A particularly trivial answer to your questions is the graph with no edges, which is also a (trivial) example of a partially ordered set.

share|cite|improve this answer
I understand your idea for a trivial example, but I do not see how you apply the finite vertices to antisymmetry, since x must be equal to y but {x,x} is not applicable. Can there be two vertices with the same label? – Jared Apr 18 '12 at 3:41
Now, to your question. We only include the edge $\{a,b\}$ when $a$ is strictly less than $b$. So when $a=b$, there is no edge between them, hence no contradiction. In particular, the edge $\{a,a\}$ is not in the graph. – Brett Frankel Apr 18 '12 at 3:50

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.