We present an automated system for deciding whether a given sentence is entailed from a body of text. Each sentence is represented as a directed graph (extracted from a dependency parser) in which the nodes represent words or phrases, and the links represent syntactic and semantic relationships. A learned graph matching cost is used to measure how much of the semantic content of the sentence is contained in the text. We present results on the Recognizing Textual Entailment (RTE) dataset (Dagan et al., 2005), compare to other approaches, discuss common classes of errors, and discuss directions for improvement.