# Find a graph with critical vertices and without critical edges.

A vertex or an edge is a critical element of a graph G if its deletion would decrease the chromatic number of G. Obviously such decrement can be no more than 1 in a graph. A critical graph is a graph in which every vertex or edge is a critical element. A k-critical graph is a critical graph with chromatic number k; a graph G with chromatic number k is k-vertex-critical if each of its vertices is a critical element

My question is how to find a graph with critical vertices and without critical edges?

• Do you want to know how to find such graphs in general, or just an example of such a graph? – Perry Elliott-Iverson May 29 '15 at 12:38

Maybe the easiest example of a graph with critical vertices and no critical edges is a star graph $G=(V, E)$ where $V=\{c, v_1, v_2, v_3, ..., v_{k}\}$ and $E=\{(c, v_1), (c, v_2), (c, v_3),...,(c,v_k)\}$. Note that the chromatic number is $2$, but if vertex $c$ is deleted then the chromatic number is $1$. However, if any edge is deleted then the chromatic number is still $2$.
A complete $k$-partite graph such that one of the partite sets has only one vertex, and each other partite set has at least 2 vertices will work. Deleting any edge will not decrease the chromatic number, but deleting the vertex in its own partite set will decrease the chromatic number.