Discrete Structure A graph is critical if the removal of any

Discrete Structure

A graph is critical if the removal of any one of its vertices (and the edges that it is incident with) reduces the chromatic number. Show Kn is critical for n>1 but Cn is critical if and only if n is odd.

Solution

1.1 Graphs Definition 1.1. A graph G is a pair G = (V, E) where V is a set of vertices and E is a (multi)set of unordered pairs of vertices. The elements of E are called edges. We write V (G) for the set of vertices and E(G) for the set of edges of a graph G. Also, |G| = |V (G)| denotes the number of vertices and e(G) = |E(G)| denotes the number of edges. Definition 1.2. A loop is an edge (v, v) for some v V . An edge e = (u, v) is a multiple edge if it appears multiple times in E. A graph is simple if it has no loops or multiple edges. Unless explicitly stated otherwise, we will only consider simple graphs. General (potentially nonsimple) graphs are also called multigraphs. Definition 1.3. • Vertices u, v are adjacent in G if (u, v) E(G). • An edge e E(G) is incident to a vertex v V (G) if v e. • Edges e, e0 are incident if e e 0 6= . • If (u, v) E then v is a neighbour of u. Example 1.4. Any symmetric relation between objects gives a graph. For example: • let V be the set of people in a room, and let E be the set of pairs of people who met for the first time today; • let V be the set of cities in a country, and let the edges in E correspond to roads connecting them; • the internet: let V be the set of computers, and let the edges in E correspond to the links connecting them. The usual way to picture a graph is to put a dot for each vertex and to join adjacent vertices with lines. The specific drawing is irrelevant, all that matters is which pairs are adjacent. 1.2 Graph isomorphism Question 1.5. 2 1 4 3 d a c b are these graphs in some sense the same? 4