Problem:Let G be a critical graph. Show that for eachseparating setS of G, the subgraph induced by S isnota complete graph.

I guess I should assume that Siscomplete, which leads to a contradiction. Could someone help me a bit with this?

Printable View

- March 12th 2009, 03:21 AMdx27Graph theory problem (critical graphs)
**Problem:**Let G be a critical graph. Show that for each*separating set*S of G, the subgraph induced by S is*not*a complete graph.

I guess I should assume that S*is*complete, which leads to a contradiction. Could someone help me a bit with this?