let G=(V,E) be a simple graph with |V|>=2. If every induced subgraph of G is connected, can you identify the graph G?
Follow Math Help Forum on Facebook and Google+
G must be a complete graph. Indeed, assume that G is not complete, so there exist at least one edge {a,b} in G'. Let's take subgraph induced by set {a,b}. This subgraph is obviously not connected. Contradiction.
View Tag Cloud