Question

The odd graph, Ok, is a graph with vertices that are the k-element subsets of (1,2,...,2k+ 5. 17. Two vertices in Ok are adjacent if and only if they are disjoint sets. (a) Draw O2 (b) What is the degree of each vertex? (c) Prove that in O2 if two vertices are not adjacent to each other, then they share a common neighbor (that is, they are both adjacent to a common vertex).

Can you explain your answer to each question so I can better understand.

Answer 1

a) Graph is drawn below:

1,3] (2,5 4,5 12,3] 1,5 1,23,5 13,4) 12,4) 11,4)

Vertices are 2-element subsets of {1,2,3,4,5} since for k=2, 2k+1=5

Examples of connected vertices {1,3} and {2,4} as they have no element in common

Examples of disconnect vertices {1,3} and {1,5} as they have "1" element common

b) Degree of each vertex is 3

c) Suppose two subsets are two vertices not adjacent to each other. Then they share a common vertex. Let the sets be {a,b} and {a,c} where the 5 elements are {a,b,c,d,e} which is some permutation of {1,2,3,4,5}

Their common neighbor is {d,e} which is adjacent to both as {a,b} and {d,e} have nothing in common as well as {a,c} and {b,d}.

Thus, if two vertices are not connected, then they share a neighbor in this graph