Combinatorics GRAPH THEORY Tress mary tree draw the two exam

Combinatorics (GRAPH THEORY)

Tress m-ary tree

draw the two examples and explain

Let T be an m-ary tree with n vertices, consisting of i internal vertices and l leaves. Suppose that m is an even number. Show that n always has to be an odd number. Give two (small) examples for the same value of m illustrating that i can be either even or odd.

Solution

T be m-ary tree with n vertices ,consisting of i internal vertices and l leaves

Each vertex in T ,other than the root ,is the child of the unique vertex

each of i internal nodes have m children ,so there are mi chidren adding the non chid vertex ,the root

we have n=mi+1

suppose m is even number

m=2x

thus n=2xi+1

since two multiple of any number is even and also even number added to 1 will give odd number

thus n is odd number

let m=4

then if i is odd

we have even multiple of odd number is even

n=4i+1        4i is even

thus 4i+1 is odd

therefore n is odd

if i is even

n=4i+1

we have 4 multiple of even number is even and added to 1 will give odd number

thus n is odd

b)

let m=6

then if i is odd

we have even multiple of odd number is even

n=6i+1        6i is even

thus 6i+1 is odd

therefore n is odd

if i is even

n=6i+1

we have 6 multiple of even number is even and added to 1 will give odd number

thus n is odd.