cnf_incidence_graph
def
The incidence graph G*(F) of a CNF formula F: the bipartite graph whose vertices are the variables of F and the clauses of F, a variable x adjacent to a clause C iff x occurs in C.
Statement
def cnf_incidence_graph {V : Type*} [DecidableEq V] (F : Finset (Finset (CnfLit V))) : SimpleGraph ({x // x ∈ cnf_vars F} ⊕ {C // C ∈ F})
- Defined in
- Short Resolution Refutations for CNFs with Bounded Weighted Incidence Treewidth, arXiv:2610.02047, Sec. 3.2 (incidence graph of a CNF formula)
- Verified
- 06 Oct 2026
- Axioms
- none listed
- Built on 3
- cnf_varsThe set var(F) of variables occurring in a CNF formula F, given as a finite set of clauses, each a finite set of literals.
- cnf_lit_varThe variable of a literal: var(x) = var(not x) = x.
- CnfLitA CNF literal over a variable type V is either a positive variable or a negated variable.
- Used by 2
- cnf_incidence_treewidthThe incidence treewidth tw*(F) of a CNF formula F: the treewidth of its incidence graph.
- cnf_incidence_treewidth_le_cardUniversal upper bound: the incidence treewidth of any CNF formula F is at most |vars(F)| + |F|.
Lean source view module on GitHub
/-- The incidence graph of a CNF formula. -/ def cnf_incidence_graph {V : Type*} [DecidableEq V] (F : Finset (Finset (CnfLit V))) : SimpleGraph ({x // x ∈ cnf_vars F} ⊕ {C // C ∈ F}) := SimpleGraph.fromRel fun a b => match a, b with | Sum.inl x, Sum.inr C => ∃ l ∈ C.1, cnf_lit_var l = x.1 | _, _ => False