1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Hard graph theory problem: please help

  1. Oct 21, 2009 #1
    If G is a connected graph with a cut-vertex v and G1 is a component of G-v, then show that the induced subgraph <V(G1)U{v}> of G need NOT be a block of G.

    I guess all I would need is a counterexample, but I can't come up with one.
  2. jcsd
  3. Oct 21, 2009 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Think of some standard examples of graphs that aren't blocks. Try connecting two of them through a single vertex
    Last edited: Oct 21, 2009
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Hard graph theory problem: please help