show that if g is simple and connected, but not complete,then g contains an indu
ID: 1891897 • Letter: S
Question
show that if g is simple and connected, but not complete,then g contains an induced path of length twoExplanation / Answer
We are given that G(V,E) is simple and connected, but not complete, so |V|>2 (because the connected graphs with orders 0, 1, or 2 are all complete), meaning G must have at least 3 vertices. Choose two adjacent points x and y of V. Because G is connected and has order greater than 2, there must exist a third vertex z distinct from x and y that is connected to either x or y (or both). This is because if x and y are not adjacent to any other vertex of G, |V|>2 guarantees that there exist more vertices of G that neither x nor y are connected to, contradicting the fact that G is connected. So the path xyz is an induced path of length two for any simple and connected G(V,E). I didn't need to use the fact that G wasn't complete; it was mostly included in the problem statement to say that G wasn't completely connected (because g obviously contains an induced path of length two or more in a connected graph with order at least 3).
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.