Let $P_n$ denote a path on $n$ vertices; $C_n$ denote a cycle on n vertices. Let $G$ be a connected simple graph that does not have $P_4$ or $C_4$ as an induced subgraph. Prove that $G$ has a vertex adjacent to all other vertices.
I'm thinking if I take a vertex of maximum degree, and then proving that that vertex must be adjacent to all other vertices, but I'm not sure how to show that just by knowing that there's no 4-cycle and there's no path with just 4 vertices. How is that even possible on a connected graph if the graph has more than 4 vertices?
Best Answer
Because there is no path over 4 vertices, and the graph is connected, 1 'middle' vertice, to which all vertices are connected.
a-b
a-b-c
a-b-c-d <- this is wrong, it has a path over 4 vertices. so d has to be added adjacent to b instead.
in this way, b has to be connected to every vertices, for if it is not there would be a path over 4 vertices.