Strong Induction, Tangled Graph

[QuietMind]

Homework Statement

Problem 1. An edge is said to leave a set of vertices if one end of the edge is in the set and the other end is not.

(a) An n-node graph is said to be mangled if there is an edge leaving every set of $\lfloor n/2\rfloor$ or fewer vertices. Prove the following claim. Claim. Every mangled graph is connected. An n-node graph is said to be tangled if there is an edge leaving every set of $\lceil n/3 \rceil$ or fewer vertices.

(b) Draw a tangled graph that is not connected.

(c) Find the error in the proof of the following

False Claim. Every tangled graph is connected.

False proof. The proof is by strong induction on the number of vertices in the graph. Let P(n) be the proposition that if an n-node graph is tangled, then it is connected. In the base case, P(1) is true because the graph consisting of a single node is trivially connected. For the inductive case, assume n ≥ 1 and P(1), . . . , P(n) hold. We must prove P(n + 1), namely, that if an (n + 1)-node graph is tangled, then it is connected. So let G be a tangled, (n + 1)-node graph. Choose $\lceil n/3 \rceil$ of the vertices and let G1 be the tangled subgraph of G with these vertices and G2 be the tangled subgraph with the rest of the vertices. Note that since n ≥ 1, the graph G has a least two vertices, and so both G1 and G2 contain at least one vertex. Since G1 and G2 are tangled, we may assume by strong induction that both are connected. Also, since G is tangled, there is an edge leaving the vertices of G1 which necessarily connects to a vertex of G2. This means there is a path between any two vertices of G: a path within one subgraph if both vertices are in the same subgraph, and a path traversing the connecting edge if the vertices are in separate subgraphs. Therefore, the entire graph, G, is connected. This completes the proof of the inductive case, and the Claim follows by strong induction.

Homework Equations

The Attempt at a Solution

I'm stuck on part c.
I find the line "Since G1 and G2 are tangled, we may assume by strong induction that both are connected" to be suspicious. I imagine a set of 4 nodes, (so n=3), where v1 is connected to each of v2, v3, v4 independently. v2, v3, and v4 have no connections between them. To my understanding, this satisfies the definition of tangling. If you say that G1 includes just v1, and G2 includes the rest, G2 is not connected. But from my understanding, in induction proofs you have to assume that the hypothesis is right, so I don't think that saying G2 is not connected constitutes a valid proof. If this is correct so far, can someone point me in the right direction?

 

[andrewkirk]

You are on the right track, because the flaw does relate to properties of the two subgraphs. But the error occurs even earlier than the line you've identified. The proof makes a statement that appears to be reasonable, but whose invalidity (of that type of statement) was pointed out by Bertrand Russell in his 'Theory of Descriptions'. A definite description is a description starting with 'the', like 'the man at the right end of the line-up'. Russell's famous example of a statement that is meaningless or false because of a false definite description is 'The present king of France is bald'. The statement assumes that there is a king of France. But Russell was writing long after the end of the French monarchy, so there was no present king of France.

Similarly with the line-up example. What if the person at the right end of the line is a woman?

A false definite description usually takes the form of saying 'The member of set S that has property P', when no member of set S has property P. eg, 'let x be the greatest number in the open real interval (0,1)'.

Can you see a definite description in the purported proof that is invalid, because it assumes without justification that a certain property holds?

 

[QuietMind]

Is G2 necessarily tangled?

Choose ⌈n/3⌉⌈n/3⌉\lceil n/3 \rceil of the vertices and let G1 be the tangled subgraph of G with these vertices and G2 be the tangled subgraph with the rest of the vertices

Right now I am suspicious of G2 being considered tangled, but I can't figure out why not. My reasoning below seems to lead me to the conclusion that it is tangled:

The parent graph G is said to be tangled. I think that guarantees any subgraphs be tangled, because then a graph of n nodes would have an edge leaving every set of $\lceil n/3 \rceil$ or fewer nodes. A subgraph would have fewer than n nodes, so the condition for tangleness would be the ceiling of fewer than n/3 nodes, which is assured by the parent's tangled status. But then, if G2 is tangled, by the induction hypothesis it is connected, and you're telling me the error is before that part of the proof.

 

[andrewkirk]

The first thing to note is that the onus is not on you to disprove unsubstantiated claims in the false proof. If a purported proof makes a claim that is not immediately obvious, and provides no justification, it fails right there.
However, it's pretty easy to show that the claim is false. The key is that G1 and G2 are subgraphs, which means that the only edges they have are amongst their own nodes. Hence any edges connecting G1 to G2 are deleted from both subgraphs.
I have drawn a tangled, connected 3-point graph that, when split into two subgraphs in a particular way, neither of the two subgraphs are tangled.