Q BgQuestion:

Scholar
Karma Points: 204
Respect (100%):
posted by  kandj on 4/24/2008 5:30:43 PM  |  status: Live  

Subgraph Relations

Course Textbook Chapter Problem
Discrete Math Mathematics: A Discrete Introduction by Scheinerman, Schneinerman N/A N/A
Question Details:
I really struggle with proofs and this one is no easier for me.
 
Which of the various properties of relations does the is-a-subgraph-of relation exhibit?  reflexive, irreflexive, symmetric, anytisymmetric and/or transitive?
 
Thanks in advance for your help!
Bonus Point Alert! Earn +4 additional karma points for helping this annual member.

AAnswers:

Answer Question
Oracle
Karma Points: 7,751
posted by gomorycut on 4/24/2008 7:59:08 PM  |  status: Live
Asker's Rating: Lifesaver   
kandj's comment:
"Thank you so much!!!"
Response Details:
It is reflexive since G is a subgraph of G for any graph G.
It is not irreflexive since it is reflexive.
 
It is not symmetric, since if H is some proper subgraph of G, then G will not be a subgraph of H.
 
It is not antisymmetric since if A is a subgraph of B, it is still possible for B to be a subgraph of A in the case that A is the same graph as B.
 
It is indeed transitive. If C is a subgraph of B and B is a subgraph of A, then it must be the case that C is a subgraph of A.

Feel free to send me a private message with any followup questions if there is something you want clarified or re-explained.

Answer Question
Ask New Question

Join Cramster's Community

Cramster.com brings together students, educators and subject enthusiasts in an online study community. With around-the-clock expert help and a community of over 100,000 knowledgeable members, you can find the help you need, whenever you need it. Join for free today » How Cramster is different than tutoring »