Courcelle's theorem is a significant result in theoretical computer science and graph theory. It states that any property of graphs that can be expressed in monadic second-order logic (MSO) can be decided in linear time for graphs of bounded tree-width. In more formal terms, if a graph has a bounded tree-width, then there exists an algorithm that can determine whether the graph satisfies a given property expressible in MSO.
New to topics? Read the docs here!