- #1

- 42

- 2

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