1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Second-order and Fixed-point Logic: Describing Graphs

  1. Apr 24, 2005 #1
    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:
  2. jcsd
  3. Apr 24, 2005 #2
    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...
  4. Apr 24, 2005 #3
    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....?
  5. Apr 24, 2005 #4
    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 : [tex] deg(v_i)=\sum_{e\in E|v_i\in e} 1[/tex]

    Then : [tex] \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 [/tex]

    The last equality sign just comes from the fact that an edges links two vertices.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Second-order and Fixed-point Logic: Describing Graphs
  1. Second-order logic (Replies: 8)