Editing Critical graph (section)

{{Short description|Undirected graph}}
{{distinguish|text=the [[Critical path method]] in project management}}
[[File:Critical graph sample.svg|right|thumb|250px|On the left-top a vertex critical graph with chromatic number 6; next all the N-1 subgraphs with chromatic number 5.]]

In [[graph theory]], a '''critical graph''' is an [[undirected graph]] all of whose proper subgraphs have smaller [[chromatic number]]. In such a graph, every vertex or edge is a '''critical element''', in the sense that its deletion would decrease the number of colors needed in a [[graph coloring]] of the given graph. Each time a single edge or vertex (along with its incident edges) is removed from a critical graph, the decrease in the number of colors needed to color that graph cannot be by more than one.