Results 1 to 2 of 2

Math Help - Even Cycles

  1. #1
    Super Member
    Joined
    Feb 2008
    Posts
    535

    Even Cycles

    Let G be a graph without even cycles or isolated vertices. Prove that every block of G
    is an edge or an odd cycle.

    Can someone show this proof? Thanks so much!!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2008
    Posts
    1,034
    Thanks
    49
    A block that isn't an edge can't have any vertices of degree one. So it must be the sum of one or more cycle graphs. And these have to be odd. Two cycle graphs must have at least two vertices in common for their sum to be a block (why?). And summing two distinct odd cycle graphs that do share at least two vertices creates ... which glitch?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. No. of cycles in graph
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 1st 2012, 01:55 AM
  2. Cycles
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 8th 2009, 07:14 PM
  3. Graphs with 4-cycles
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 23rd 2009, 10:26 PM
  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