Let the "n" vertices of the given graph "G" be "v"1, "v"2, . . . , "v"n. The Mycielski graph μ("G") contains "G" itself as a subgraph, together with "n"+1 additional vertices: a vertex "u""i" corresponding to each vertex "v""i" of "G", and an extra vertex "w". Each vertex "u""i" is connected by an edge to "w", so that these vertices form a subgraph in the form of a star "K"1,"n". In addition, for each edge "v""i""v""j" of "G", the Mycielski graph includes two edges, "u""i""v""j" and "v""i""u""j".