Results 1 to 4 of 4

Math Help - Graphy Theory Question about Blocks

  1. #1
    Newbie
    Joined
    Aug 2012
    From
    USA
    Posts
    16

    Question Graphy Theory Question about Blocks

    Hi how would you go about solving the following question:

    Prove that if G is a graph of order n >= 3 with delta(G) >= n/2, then G is a block.

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,790
    Thanks
    1687
    Awards
    1

    Re: Graphy Theory Question about Blocks

    Quote Originally Posted by Johnyboy View Post
    Hi how would you go about solving the following question:
    Prove that if G is a graph of order n >= 3 with delta(G) >= n/2, then G is a block.
    You need to provide some definitions.
    What is a block?
    What does \delta(G) stand for?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Aug 2012
    From
    USA
    Posts
    16

    Re: Graphy Theory Question about Blocks

    A block is a maximal connected non-separable graph, stated differently a connected graph that contains no cut-vertices and is not properly contained in a subgraph with no cut-vertices and delta(G) = min{deg v: v in V(G)}. Thanks.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Aug 2012
    From
    USA
    Posts
    16

    Re: Graphy Theory Question about Blocks

    I tried an approach using induction but I got stuck. I did the following:

    Start of induction process:
    Let n=3, then delta(G) >= n/2, it follows that the lowest degree of a vertex is 2. Therefore G has no end-vertices, therefore G is not a tree and G must contain at least one cycle C_k. It follows that since the order of G is 3, G is the cycle C_3 and is therefore a block.

    Assume that n > 3 and the result is true for graphs of order less than n.

    My idea is to take a graph of order n with delta(G) >= n/2 and then remove some vertex v, which gives us a graph G-v of order n-1 with delta(G-v) >= (k-1)/2, apply the induction hypothesis to conclude that G-v is a block and then show that if we add vertex v again then G is still required to be a block.

    One of my main problems is that I am not sure how to specify the vertex v that I want to remove in order to ensure that G-v satisfies delta(G-v) >= (k-1)/2 so that I can use the inductive hypothesis.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Random blocks that fit together
    Posted in the Geometry Forum
    Replies: 0
    Last Post: September 18th 2011, 10:11 AM
  2. Jordan blocks
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: May 12th 2011, 12:14 AM
  3. Replies: 0
    Last Post: April 9th 2011, 08:57 AM
  4. Permutations question - 4k blocks
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: July 24th 2009, 12:20 AM
  5. graphy theory
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 21st 2008, 06:56 PM

Search Tags


/mathhelpforum @mathhelpforum