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.

Improve this question
$\endgroup$
1
  • 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, 2018 at 9:15

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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