0
$\begingroup$

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.

1 Answers 1

1

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. A particularly trivial answer to your questions is the graph with no edges, which is also a (trivial) example of a partially ordered set.

  • 0
    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.2012-04-18