discreet,1) Suppose a box contains 18 balls numbered 1 through 6, three balls with each number.

Question

1) Suppose a box contains 18 balls numbered 1 through 6, three balls with each number. When 5 balls are drawn without replacement, how many outcomes are possible, a) if the order in which the balls are drawn matters? b) if order does not matter?

2) Draw all connected graphs of order 5 in which the distance between every two distinct vertices is odd.

3) Draw three non-isomorphic graphs of order 5 and size 5.

4) Show by an example that a graph of order n and size n-1 need not be a tree.

Answer 1

a) P(18,15) = 18 * 17 * 16 * 15 * 14

b) 18C 5 = 18!/ 5! * 13!

c) a graph of order and size 5 edges.

d) A tree is a connected graph with no cycles.

A tree with

nn

𝑛

vertices always has

n−1n minus 1

𝑛−1

edges.

However, a graph with

nn

𝑛

vertices and

n−1n minus 1

𝑛−1

edges is not necessarily a tree if it is not connected.

An example for n=5n equals 5

𝑛=5

: Consider a graph with

55

5

vertices and

44

4

edges.

Let the vertices be V={v1,v2,v3,v4,v5}cap V equals the set v sub 1 comma v sub 2 comma v sub 3 comma v sub 4 comma v sub 5 end-set

𝑉={𝑣1,𝑣2,𝑣3,𝑣4,𝑣5}

.

Construct a cycle

C3cap C sub 3

𝐶3

using vertices

v1,v2,v3v sub 1 comma v sub 2 comma v sub 3

𝑣1,𝑣2,𝑣3

with edges (v1,v2),(v2,v3),(v3,v1)open paren v sub 1 comma v sub 2 close paren comma open paren v sub 2 comma v sub 3 close paren comma open paren v sub 3 comma v sub 1 close paren

(𝑣1,𝑣2),(𝑣2,𝑣3),(𝑣3,𝑣1)

.

This uses

33

3

vertices and

33

3

edges.

Add an edge (v4,v5)open paren v sub 4 comma v sub 5 close paren

(𝑣4,𝑣5)

.

This adds

22

2

more vertices and

11

1

more edge.

The resulting graph has

55

5

vertices and

3+1=43 plus 1 equals 4

3+1=4

edges.