Help with graph theory

Kipster1203

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?

Office_Shredder

Any connected subgraph containing u and v has to contain a set of vertices/edges satisfying what property?

Kipster1203

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?

Office_Shredder

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

Kipster1203

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?

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

Kipster1203

a path of length 1?

Office_Shredder

That probably doesn't exist (unless u and v are connected)

Kipster1203

Oh because it says u and v are distinct, so the smallest that could exist would have length 2

Office_Shredder

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

Kipster1203

yes, that is one example. But the question asks for the minimum size.

Office_Shredder

I'm confused. Yes, it's an example, and the point is that the answer is not always two