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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook