142 CHAPTER 2 Discrete Mathematics
- Here’s a slightly more sophisticated problem. Define the graphsG 1
andG 2 , as follows. Start by lettingnbe a fixed positive integer.
Vertices ofG 1 : These are the subsets of{ 1 , 2 , ..., n}.
Edges ofG 1 : {A, B}is an edge ofG 1 exactly when|A∩B| = max{|A|− 1 ,|B|− 1 }.(Notice that this says that eitherA⊆Band|B|=|A|+ 1 or
thatB⊆Aand that|A|=|B|+ 1.)
Vertices ofG 2 : These are thebinary sequencesv= ( 1 , 2 ,...,n),
where eachi= 0 or 1.
Edges ofG 2 : {v, w} is an edge ofG 2 precisely when the binary
sequences definingv andwdiffer in exactly one place. (This
is the graph defined in Exercise 6 on page 116.)Show that the graphsG 1 andG 2 are isomorphic.- Assume that a graph Gcan be “faithfully” drawn on the surface
of a sphere. Must this graph be planar? - Consider the “grid graph,” constructed as follows. Let m andn
be positive integers and in the coordinate plane mark the points
havinginteger coordinates(k,l) such that 0≤k≤mand 0≤n≤
m. These are the vertices of the graphG. The edges in this graph
connect the vertices separated by Euclidean distance 1. Show that
this graph is bipartite.