# Second-order and Fixed-point Logic: Describing Graphs

• nounou
In summary, The conversation is about representing certain properties of a graph using second-order logic versus fixed-point logic, specifically the idea of a graph having an even number of edges. The participants discuss different approaches and functions to express this property mathematically. One suggestion is to use the function Degree(edge(X,Y)) and another is to define the degree of a vertex and its relation to the sum of degrees in the graph. In the end, the mathematical representation of a graph is summarized as a pair of sets of vertices and edges.
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 ? :yuck:

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

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...?

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.

## 1. What is second-order logic and how does it relate to describing graphs?

Second-order logic is a type of mathematical logic that allows quantification over both individual objects and sets of objects. It is particularly useful for describing properties of graphs, as it allows for the quantification over subgraphs and sets of vertices or edges.

## 2. How is fixed-point logic used in describing graphs?

Fixed-point logic is a type of second-order logic that allows for the definition of recursive functions. In terms of describing graphs, fixed-point logic can be used to define graph properties that are defined in terms of themselves, such as connectivity or cycles.

## 3. What are some common applications of second-order and fixed-point logic in graph theory?

Second-order and fixed-point logic are commonly used in graph theory to define and prove properties of graphs, such as connectivity, planarity, and colorability. They are also used in algorithm design and optimization problems on graphs.

## 4. Can graphs be fully described using second-order and fixed-point logic?

No, second-order and fixed-point logic are powerful tools for describing properties of graphs but they cannot fully capture all aspects of a graph. For example, they cannot describe properties that are dependent on the specific structure of a graph, such as the shortest path between two vertices.

## 5. Are there any limitations to using second-order and fixed-point logic in describing graphs?

One limitation of second-order and fixed-point logic is that they are not decidable, meaning there is no algorithm that can determine whether a given logical statement is true or false. This can make it difficult to use in automated reasoning and decision-making processes.

• Set Theory, Logic, Probability, Statistics
Replies
11
Views
488
• Set Theory, Logic, Probability, Statistics
Replies
40
Views
6K
• Set Theory, Logic, Probability, Statistics
Replies
4
Views
2K
• Set Theory, Logic, Probability, Statistics
Replies
4
Views
2K
• Set Theory, Logic, Probability, Statistics
Replies
2
Views
2K
• Set Theory, Logic, Probability, Statistics
Replies
16
Views
4K
• Introductory Physics Homework Help
Replies
10
Views
1K
• Programming and Computer Science
Replies
2
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
45
Views
3K
• Introductory Physics Homework Help
Replies
1
Views
433