Second-order and Fixed-point Logic: Describing Graphs

[nounou]

Does anyone have an idea how can we represent certain properties of a graph using
second-order logic, versus fixed-point logic :

like saying that a graph has an even number of edges

I've been trying to find a way to solve this for the past two days !

Any help?

Anyone ?

 

[kleinwolf]

Counterexample : Take the graph A-B...this one has only 1 edge...

I suppose you want to say : the sum of the degrees in a graph is even (the degree of a vertex is the sum of edges arriving at that vertex).

This is simply because the sum of the degree of each vertex is 2*n_edges...

 

[nounou]

Thanx Kleinwolf,
So you think i would use another function Degree(edge(X,Y)) ? But how how will I say mathematically that the sum is even Sigma Degree(edge(X,Y)) = 2*n...?

 

[kleinwolf]

If I remember well, with symbols loved by mathematicians, a graph is a pair of set G=(V,E). The elements of V are the vertices v_i. The elements of E are the edges e_i=(v_1,v_2), linking vertices v_1 with v_2.

The degree of a vertex v_i is defined by : deg(v_i)=\sum_{e\in E|v_i\in e} 1

Then : \sum_i deg(v_i)=\sum_{v_i\in V}\sum_{e\in E|v_i\in e}1=\sum_{e\in E}\sum_{v_i\in V|v_i\in e}1=\sum_{e\in E}2

The last equality sign just comes from the fact that an edges links two vertices.