<p>Parity cannot be expressed in MSOL (see for instance <a href="http://www.cs.technion.ac.il/~janos/COURSES/236331-15/Lec-1.pdf" rel="noreferrer">http://www.cs.technion.ac.il/~janos/COURSES/236331-15/Lec-1.pdf</a>), 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. </p>

CC BY-SA 3.0
2018-02-21T10:06:18.700Z
2018-02-21T10:06:18.700Z
M. kanté
<p>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). </p>

<p>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.</p>

CC BY-SA 3.0
2018-02-21T09:15:08.330Z
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?
Gamow
<graph-theory><lo.logic><finite-model-theory>
Is Eulerian Path (or Eulerian Cycle) definable in Monadic Second Order Logic?
Aalok Thakkar
# Is Eulerian Path (or Eulerian Cycle) definable in Monadic Second Order Logic?

(Asked by: username_0 on 2018-02-21)

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.

**Tags:** graph-theory, lo.logic, finite-model-theory
> **Comments:**
> **username_1**: 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?  

---

## 1 answers

### Answer by username_2 on 2018-02-21. Score: 7

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.


---

