0
$\begingroup$

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!

Improve this question
$\endgroup$
  • 7
    $\begingroup$ How does knowing the n-1 graph is connected imply the n-graph is connected? $\endgroup$ – Air Conditioner Jan 14 '18 at 13:43
  • $\begingroup$ @Useless Seems that a comment below shows how this could be done beginning with $n=2$. Of course, the author should have mentioned this possibility. $\endgroup$ – Peter Jan 14 '18 at 14:11
1
$\begingroup$

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.

Improve this answer
$\endgroup$
  • $\begingroup$ Let's suppose the claim is true for $n=2$. 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 more than I need). 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$. Am I wrong ? $\endgroup$ – Tal Singrist Jan 14 '18 at 14:06
  • $\begingroup$ "In the case of the horses with the same colours the truth for n=2 would actually imply that all horses have the same colour" That's where the "all horses have the same color" fake-proof fails. $\endgroup$ – Tal Singrist Jan 14 '18 at 14:07
  • $\begingroup$ Seems that the argument is valid. Please add it to your answer. $\endgroup$ – Peter Jan 14 '18 at 14:09
1
$\begingroup$

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

Improve this answer
$\endgroup$
  • $\begingroup$ This shows that the induction proof must have a flaw, but it doesn't reveal where the flaw is. $\endgroup$ – Peter Jan 14 '18 at 14:16
  • $\begingroup$ The flaw is assuming that argument holds for $n$ vertices and removing a vertex to make argument true. In induction, implication is as $P(n-1) \implies P(n)$, even if there is a induction method by using an implication $P(n) \implies P(n-1)$, I don't think it starts with a smallest base case (as far as I know, there isn't). And I also give a counter-example that $P(n) \implies P(n-1)$ doesn't have to work in this case. $\endgroup$ – ArsenBerk Jan 14 '18 at 14:23
  • 4
    $\begingroup$ @Peter Well there are versions of the proof where the flaw is subtle or interesting. But in the proof as given in the OP the flaw is just that there's simply no justification for the "therefore the original graph is ocnnected". This answer does reveal that that "therefore" is wrong - we can't say where the OP went wroong in concluding it was correct because he omits his reasoning fpr that step. $\endgroup$ – David C. Ullrich Jan 14 '18 at 15:14
0
$\begingroup$

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$.]

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.