# Construct a graph G for which the is-adjacent-to relation is antisymmetric.

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.

-

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.
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