# Help with graph theory

1. Sep 23, 2010

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

2. Sep 23, 2010

### Office_Shredder

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

3. Sep 23, 2010

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

4. Sep 23, 2010

### Office_Shredder

Staff Emeritus
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

5. Sep 23, 2010

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

6. Sep 23, 2010

### Office_Shredder

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

7. Sep 23, 2010

### Kipster1203

a path of length 1?

8. Sep 23, 2010

### Office_Shredder

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

9. Sep 23, 2010

### Kipster1203

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

10. Sep 23, 2010

### Office_Shredder

Staff Emeritus
Consider the following graph

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

11. Sep 23, 2010

### Kipster1203

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

12. Sep 23, 2010

### Office_Shredder

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