Graph Theory Proof: Number of Vertices and Edges in a Connected Graph

[beddytear]

Homework Statement

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.

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

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.
thanks in advance.

 

[Office_Shredder]

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

 

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

 

[Office_Shredder]

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

 

[beddytear]

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

 

[Office_Shredder]

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