2
$\begingroup$

Does there exist a monadic second order logic formula which is satisfied by a graph if and only if it has an Eulerian path (or Eulerian cycle).

I am looking for properties of graphs which are polynomial time testable but cannot be defined in MSO. I am more inclined to examples of properties from standard textbooks as it is meant for a CS (engineering) crowd and not a CS theory crowd.

$\endgroup$
  • 3
    $\begingroup$ Just think for your self: (1) is it possible to express connectivity in MSOL? (2) Is it possible to express the even degree condition in MSOL? $\endgroup$ – Gamow Feb 21 '18 at 9:15
7
$\begingroup$

Parity cannot be expressed in MSOL (see for instance http://www.cs.technion.ac.il/~janos/COURSES/236331-15/Lec-1.pdf), but connectedness Yes. Using instead $C_2$MSOL, one can express the existence of an eulerian cycle by using the equivalent characterisation : connected and every vertex has degree even.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.