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?

Printable View

- Dec 2nd 2009, 09:19 PMsbankicainduced subgraphs
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?

- Dec 3rd 2009, 02:58 AMsidor
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.