Proving a mangled graph to be connected.

Question

In MIT's 6.042J course, there is a question in assignment 5 problem 3 c.

An n-node graph is said to be mangled if there is an edge leaving every >set of n/2 or fewer vertices. Again, as a special case, the graph >consisting of a >single node is considered mangled. Prove the following >claim. Hint: Prove by contradiction. Claim. Every non-empty, mangled graph is connected.

I couldn't prove it by contradiction, so I attempted to prove it by induction. Is my proof correct? How can I prove it by contradiction?

Pf (By induction on number of nodes of the graph):

Base Case (P(1)): A 1-node graph is mangled and it is connected.

Inductive Step, assume P(n) to prove induction hypothesis:

Assuming an n-node mangled graph is connected. If we added one node to this graph, we get an n+1-node graph.

Now taking this added node as a group. Since the graph is mangled, therefore this group (containing only one node) must have an edge leaving it. So, this node is connected to the former n-node graph.

Answer 1

Proof by contradiction.

Suppose such a graph (with $n$ vertices) is not connected. Then it has at least two components. At least one component must have at most $\frac n2$ vertices. No edge is leaving this component. Contradiction.

Answer 2

Your proof is not correct. First of all, you need to know that your new graph is mangled before you can conclude that there's an edge leaving it.

Second, you're working backwards: To do an inductive proof, you'd want to start with an n+1=node mangled graph and then try to show it's connected by (1) showing there's an n-node mangled subgraph (which will be connected by the induction hypothesis) and (2) showing that the last node is connected to this subgraph.

I don't see an easy way to do this particular inductive proof, so this is just a sketch of the SHAPE of such a proof, not a claim that such a proof can be constructed.