# Devising a way to spot a contradiction given a set of statements using graphs

If we had statements like: John is as tall as Mark, Mark is as tall as Sally, Chuck is as tall as Sally, Chuck is shorter than John.

Would there be a way to figure out that there is a contradiction in this set of statements using graphs?

My attempt at it was to symbolize each of the names, assuming they have different first letters to statements like, J = M, M = S, C = S, C ≠ J.

My idea is to find a cycle after using DFS on some graph but I'm having trouble making the actual graph which is perhaps the most troublesome part.

I hope I'm on the right track. Any help would be much appreciated!

Edit: The comment makes a good point and the statements do have inequalities as well, but I'd like to make another attempt at that on my own afterwards. If the question were to be simplified to just "as tall" and "not as tall", what sort of graph would I make?

• C < J instead of C $\not=$ J. – Apass.Jack Mar 20 at 3:37
• Oops, I forgot to mention that, thanks! I've edited my post to address that. – SunnySideUp Mar 20 at 3:40
• Have you heard of directed graph? Equivalence class? – Apass.Jack Mar 20 at 3:45
• Unfortunately, I haven't. I did some googling just now and am a little overwhelmed as I'm unfamiliar with the strongly connected terminology as well... – SunnySideUp Mar 20 at 3:48
• I suggest getting a good algorithms textbook and reading about strongly connected components, and algorithms for finding them. Then, work through a small example (make the graph, find the SCCs), and I think you'll discover that these concepts are exactly what you need. – D.W. Mar 20 at 5:40

Next you can consider the "<" and ">" relationships. You can treat each connected component as a vertex and add directed edges so that $$(u,v)$$ represents the relationship $$u. Then you can detect if there is a cycle in the directed graph by DFS again. If there is cycle, there is a contradiction among these relationships; otherwise the relationships we processed so far are consistent.
At last you can consider the "$$\neq$$" relationships. You can simply check for each relationship $$a\neq b$$ if $$a$$ and $$b$$ belong to the same connected component. If $$a$$ and $$b$$ belong to different connected components for all relationships $$a\neq b$$, then all the relationships are consistent; otherwise there is a contradiction.