Results 1 to 2 of 2

Math Help - Graphs with 4-cycles

  1. #1
    Member
    Joined
    Oct 2008
    Posts
    130

    Graphs with 4-cycles

    Let G be a simple graph with 28 edges and 10 vertices.

    Show that G contains a 4-cycle.

    My first idea is to observe that at least one vertex must have degree 3.

    Then I examine three branches coming from degree 3 and I try to show that we find a cycle there (involve the degree at least 3 vertex or the branch). But I can't see how to do that.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2009
    Posts
    277
    Thanks
    2

    Questions

    Can you assume this is a planar graph? If so, you have Euler's relation to play with.

    Is the question the existence of a 4 or more cycle, or exactly a 4-cycle?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Even Cycles
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 27th 2010, 11:06 AM
  2. Cycles
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 8th 2009, 07:14 PM
  3. Number of directed graphs with no cycles
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: May 23rd 2009, 05:18 AM
  4. cycles
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: November 22nd 2008, 09:01 PM
  5. cycles
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: October 9th 2008, 05:08 PM

Search Tags


/mathhelpforum @mathhelpforum