Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Help with graph theory

  1. Sep 23, 2010 #1
    Let u and v be distinc vertices in a connected graph G. There may be several connected subgraphs of G containing u and v. What is the minimum size of a connected subgraph of G containing u and v?

    and does this suggest another question?
     
  2. jcsd
  3. Sep 23, 2010 #2

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Any connected subgraph containing u and v has to contain a set of vertices/edges satisfying what property?
     
  4. Sep 23, 2010 #3
    that they are connected.

    Size is the number of edges right? So if the subgraph only contained adjacent u and v, then wouldn't the minimum size be 1?
     
  5. Sep 23, 2010 #4

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I already said the subgraph is connected. What does it mean for that to be true?

    Size can be referring to either the number of edges or the number of vertices depending on context. I'm not sure which one they mean here, but it turns out to be the same answer regardless
     
  6. Sep 23, 2010 #5
    The number of vertices is the defined as the order of a graph.

    A graph is said to be connected when a path exists between every pair of vertices?
     
  7. Sep 23, 2010 #6

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    And a path is a special kind of a connected graph. So every connected subgraph containing u and v contains a path from u to v, which means the smallest connected subgraph must be...
     
  8. Sep 23, 2010 #7
    a path of length 1?
     
  9. Sep 23, 2010 #8

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    That probably doesn't exist (unless u and v are connected)
     
  10. Sep 23, 2010 #9
    Oh because it says u and v are distinct, so the smallest that could exist would have length 2
     
  11. Sep 23, 2010 #10

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Consider the following graph

    http://www.cs.ucr.edu/~neal/2005/cs141/wikidb/uploads/cut_vertices.png

    Ignoring the other stuff on the pictures, what's the size of the smallest connected subgraph containing a and h? It certainly isn't two; that implies that they are connected by an edge
     
  12. Sep 23, 2010 #11
    yes, that is one example. But the question asks for the minimum size.
     
  13. Sep 23, 2010 #12

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I'm confused. Yes, it's an example, and the point is that the answer is not always two
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook