Definition
Incidence Graph (Propositional Logic)
The incidence graph of a CNF formula
is the bipartite graph whose vertex set consists of the variables of and the clauses of . A variable vertex is adjacent to a clause vertex exactly if occurs in , either positively as or negatively as . Example: For the formula
the incidence graph has variable vertices
and clause vertices , where together with the edges
, , , , , and . The corresponding incidence graph is: