Results 1 to 2 of 2

Math Help - Graph theory - perfect matching using Petersen's theorem

  1. #1
    Newbie
    Joined
    Sep 2009
    Posts
    3

    Graph theory - perfect matching using Petersen's theorem

    HI guys ,

    I have a little problem regarding Perfect Matching .
    I have a graph G=(V,E) with |V|=2n and δ(G)>=n (where δ(G) is the minimal degree
    for each vertex) .
    Now I need to prove that G has a perfect matching .

    I tried to use Perersen's theorem for 3-regular graph but I kinda got lost (Petersen graph - Wikipedia, the free encyclopedia

    can I say that if I separate the 2n vertexes that I have to 2 groups , S and T ,
    then that the worst case scenario would be that : S would have at least two
    neighbors in T , and further more , that there would be NO bridges ?

    I cannot understand why , if we take some vertex , in would have a least two neighbors ??!!

    if so , then now I want to use Petersen's theorem : if there are no bridges , is it right to say that any n-regular graph would have a 3-regular graph ?

    I'll appreciate your help
    thanks (:
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member Traveller's Avatar
    Joined
    Sep 2010
    Posts
    162
    Here is a different approach:

    We use Tutte's theorem for the proof: Tutte theorem - Wikipedia, the free encyclopedia

    We make a stronger claim : For any graph G(V,E) with |V|=2n and \delta (v) \geq n, for any subset S of V, the number of components in V\S is at most |S|.

    Proof:The claim is obvious for |S| \geq n.

    For some S' such that S' < n, let |S'| = s. Let us assume that the number of components in V / S is more than s.

    Due to the lower bound on the minimum degree, the size of each component must be at least ( n + 1 - s ). So the total number of vertices in G is at least : (s + 1)(n + 1 - s) + s  = -s^2 + s( n + 1 ) + ( n + 1 ). Differentiating this function with respect to s, we find that it attains only one local extremum which is a maximum point at s = \frac{n+1}{2}. Since it evaluates to (2n + 1) at both s=1 and s=n, it cannot have a lesser value in between.

    This proves the claim and the required result follows by Tutte's theorem.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. proof of cayley's theorem; graph theory
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 15th 2011, 09:21 AM
  2. automorphism group of the Petersen graph
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 10th 2011, 04:38 PM
  3. a theorem in graph theory.. please help
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: May 8th 2011, 10:22 AM
  4. Replies: 0
    Last Post: September 25th 2010, 05:59 AM
  5. Graph Theory [Menger's Theorem]
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 27th 2008, 01:29 PM

Search Tags


/mathhelpforum @mathhelpforum