---
tag: KHQMTVDM6V
kind: concept
name: Pfaffian orientation
sources:
  - wikipedia: en:56281176@r1364456348
    locator: Pfaffian orientation
    note: adopted
    mention: wikipedia://en/56281176
    sections: [Summary]
same_as:
  wikidata: Q49000601
  wikipedia: Pfaffian orientation
inventory: [WGCJSWGJRT]
---

## Summary

In graph theory, a **Pfaffian orientation** of an undirected graph assigns a direction to each edge, so that certain cycles (the "even central cycles") have an odd number of edges in each direction. When a graph has a Pfaffian orientation, the orientation can be used to count the [[perfect matchings|05ZPH8KF9K]] of the graph. This is the main idea behind the FKT algorithm for counting perfect matchings in [[planar graphs|029JQEK15B]], which always have Pfaffian orientations. More generally, every graph that does not have the utility graph $K_{3,3}$ as a graph minor has a Pfaffian orientation, but $K_{3,3}$ does not, nor do infinitely many other minimal non-Pfaffian graphs.