116 CHAPTER 2 Discrete Mathematics
- We consider the following family of simple graphsOn, n= 1, 2 ,...,
defined as follows.
Vertices: The set of vertices is the set{± 1 ,± 2 , ...,±n}.
Edges: The vertex i is adjacent to the vertex j precisely when
|i|6=|j|.(a) Draw the graphsO 1 , O 2 , O 3.
(b) What is the degree of every vertex inOn?
(c) Is there an Eulerian circuit inOn, n >1?- We consider the family of graphs Cn, n= 1, 2 ,...defined as fol-
lows.
Vertices: The set of vertices is the set of binary sequences
v= ( 1 , 2 ,...,n), where eachi= 0 or 1.
Edges: The vertex v is adjacent to the vertexw precisely when
the binary sequences defining v andw differ in exactly one
place.The graphC 3 is indicated to the right.(a) What is the degree of each vertex inCn, n≥1?
(b) How many paths are there from the vertex (0, 0 ,...,0) to the
vertex (1, 1 ,...,1)?