1. PF Contest - Win "Conquering the Physics GRE" book! Click Here to Enter
    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 Threads - Hard graph theory Date
Hairy trig integral Mar 3, 2018
Have to find the stationary points on the graph y = 3sin^2x Feb 14, 2018
Hard Double Integral Nov 9, 2017
Hard to differentiate Oct 15, 2017
Integral form of Particular solution question Apr 30, 2017