## Help with graph theory

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?
 PhysOrg.com science news on PhysOrg.com >> City-life changes blackbird personalities, study shows>> Origins of 'The Hoff' crab revealed (w/ Video)>> Older males make better fathers: Mature male beetles work harder, care less about female infidelity
 Blog Entries: 1 Recognitions: Homework Help Any connected subgraph containing u and v has to contain a set of vertices/edges satisfying what property?
 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?

Blog Entries: 1
Recognitions:
Homework Help

## Help with graph theory

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

 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?
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
 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?

Blog Entries: 1
Recognitions:
Homework Help
 A graph is said to be connected when a path exists between every pair of vertices?
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...

 Quote by Office_Shredder 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...
a path of length 1?

Blog Entries: 1
Recognitions:
Homework Help
 Quote by Kipster1203 a path of length 1?
That probably doesn't exist (unless u and v are connected)

 Quote by Office_Shredder That probably doesn't exist (unless u and v are connected)
Oh because it says u and v are distinct, so the smallest that could exist would have length 2

Blog Entries: 1
Recognitions:
Homework Help
 Oh because it says u and v are distinct, so the smallest that could exist would have length 2
Consider the following graph

http://www.cs.ucr.edu/~neal/2005/cs1...t_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
 yes, that is one example. But the question asks for the minimum size.
 Blog Entries: 1 Recognitions: Homework Help I'm confused. Yes, it's an example, and the point is that the answer is not always two

 Similar discussions for: Help with graph theory Thread Forum Replies General Math 4 Calculus & Beyond Homework 0 Calculus & Beyond Homework 0 General Math 0 Calculus & Beyond Homework 2