Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

1 Answer 1

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|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
1  
The point of this site is to help people understand, not provide solutions to homework problems! That said, feel free to post homework problems you are stuck on, but in the future please use the homework tag. You will find the people on this site more than happy to provide helpful, instructive hints that will be much more beneficial in the long run than ready-made solutions. –  Brett Frankel Apr 18 '12 at 3:48
    
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

 
discard

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.