Minimum Size of Connected Subgraph in Graph Theory | Help with u and v in G

[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]

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

 

[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]

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

 

[Kipster1203]

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?

 

[Office_Shredder]

a path of length 1?

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

 

[Kipster1203]

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

 

[Office_Shredder]

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

 

[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