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

688 Views Asked by At

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

There are 1 best solutions below

2
On BEST ANSWER

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.