Fake induction, can't find flaw, every graph with zero edges is connected

Question

I have the folowing induction :

"Every graph with n vertices and zero edges is connected"

• Base:

  For $n=1$ graph with one vertice is connected, hence a graph with $1$ vertex and zero edge.

• Assumpution:

  Every graph with $n-1$ vertices and zero edges is connected.

For every graph with $n$ vertices and zero edges lets remove one vertice hence we get a graph with $n-1$ vertices and zero edges, by the assumpution the graph is connected, therefore the original graph is connected.

I feel that when we remove one vertice from the graph with $n$ vertice it not must be a connected graph, Yet I'm not sure if thats the flaw, or how to proof it.

I read about the "all horses has the same color" yet I don't find how to use the method of it here.

Any ideas?

Thanks!

Answer 1

The flaw is when you use this sentence : For every graph with n vertices and zero edges lets remove one vertice hence we get a graph with n−1 vertices and zero edges, by the assumpution the graph is connected, therefore the original graph is connected

for n = 2. It doesn't work : you get 2 "1 vertice" graph, and nothing to tell about them. As in the all horses have the same color (twice "one horse has the same color as himself" doesn't proove that "2 horses have the same color").

For the proof to be correct, your base should be proven for $n$=2, not for $n$=1.

If you were able to prove the base for $n=2$, then you would be able to prove if for every integer :

Let suppose $P_2$ = "every (2-vertices,0 edge) graph is connected" is true, and then we can demonstrate $P_3$ = "every (3-vertices,0 edge) graph is connected"

Be $G$ a graph with 3 vertices ($V_1$ , $V_2$ and $V_3$) and zero edge. You can split $G$ in 3 graphes of 2 vertices (and zero edge each). By the assumption all those 3 graphes are connected (it's even more than needed). So there is a path from $V_1$ to $V_2$, a path from $V_2$ to $V_3$, and hence a path from $V_1$ to $V_3$ passing by $V_2$.

And so on...

But this kind of demonstration, you cannot do if you only suppose that $P_1$ = "every (1-vertice,0 edge) graph is connected" is true - you'll never be able to demonstrate $P_2$ = "every (2-vertices,0 edge) graph is connected" is true.

With just $P_1$ true : Be $G$ a (2-vertices,0 edge) graph. By $P_1$ you can just say that each vertice is connected to itself , which is obvious and doesn't even need $P_1$ , but nothing more.

Answer 2

The problem is here:

For every graph with $n$ vertices and zero edges lets remove one vertice hence we get a graph with $n−1$ vertices and zero edges, by the assumpution the graph is connected, therefore the original graph is connected.

Because first you supposed argument holds for $n-1$ vertices. Then you start with $n$ vertices and removed one to make your assumption true. But this doesn't imply that the graph with $n$ vertices is connected. For example, if you remove a vertex, that is not a leaf, from a tree you get a disconnected graph even though tree is connected itself. Instead, you should use induction as this one (after the base case):

Suppose the argument holds for $n-1$. Then if we add a vertex to have a graph with $n$ vertices, ...

However, when we add an isolated vertex (not connected to any other $n-1$ vertices), then by definition of connectivity, the graph with $n$ vertices will not be connected. So argument doesn't hold for all $n$.

Answer 3

The induction step (from $n-1$ to $n$, or from all '$k < n$' to $n$) is missing here. All you've done is proven that

if all graphs of n-1 nodes with no edges are connected, then all graphs with n nodes and zero edges have a connected subgraph of n-1 nodes and no edges. 

That's really not very interesting! From your basis $n=1$, you have proved successfully that the graph with $n=2$ vertices and no edges has a subgraph with one vertex that is connected. But that's ALL you've proved. [You would need to replace the basis step with $n=2$ to prove $n=3$, and the basis step obviously fails for $n=2$.]