# Graph theory proof help

1. Nov 5, 2009

### beddytear

1. The problem statement, all variables and given/known data

Let G be a graph with at least two vertices, such that the cut induced by every
proper nonempty subset of vertices of G contains exactly two elements. Determine
(with proof ) the number of vertices and edges in G.

2. Relevant equations

Connectedness. A graph G is connected if for any two vertices x and y in G, there is a path from x to y.

3. The attempt at a solution
I'm really stuck. But i think proving by contradiction is a good approach (maybe??).
i.e.: Suppose the graph is not connected...i.e. it has more than one component. ......?????
this is a contradiction...therefore the graph is connected?
like i said. i'm really having troubles. any help would be greatly appreciated.
1. The problem statement, all variables and given/known data

2. Relevant equations

3. The attempt at a solution

2. Nov 5, 2009

### Office_Shredder

Staff Emeritus
What do you mean by the cut induced...? I don't remember hearing that specific usage of the word cut regarding graph theory but I may have just forgotten

3. Nov 5, 2009

### beddytear

Given a subset X of the vertices of G, the cut induced by X is the set of edges that have exactly one end in X.

Maybe the theorem: A graph G is not connected if and only if there exists a proper nonempty subset X of V(G) such that the cut induced by X is empty helps?

4. Nov 5, 2009

### Office_Shredder

Staff Emeritus
Ok, so you're given a graph G. For any subset of G, say X, there are exactly two edges going from X to G-X

Start by picking a single vertex in G and notice that if X is a single vertex, that vertex has to have degree 2. What are your possible choices for G? Then by picking other subsets X narrow it down further

5. Nov 6, 2009

### beddytear

still lost. if i pick 2 vertices...?????? 3 vertices???

6. Nov 6, 2009

### Office_Shredder

Staff Emeritus
It will help if you write down exactly what the set of all possible connected graphs are for which every vertex has degree 2