Week 7

Question 1

Give the definition of homomorphism. Let G and H be graphs

Answer 1

Let 𝐺 and 𝐻 be graphs. Suppose that 𝑓 is a function from 𝑉(𝐺) into 𝑉(𝐻). We say that
𝑓 is a homomorphism if and only if, for all 𝑢, 𝑣 ∈ 𝑉(𝐺), if {𝑢, 𝑣} ∈ 𝐸(𝐺), then
{𝑓(𝑢), 𝑓(𝑣)} ∈ 𝐸(𝐻).

Question 2

Explain homomorphism in simple terms

Answer 2

A homomorphism is a function that sends every edge of
𝐺 to an edge of
𝐻

Question 3

What is the identity function?

Answer 3

a function that sends every element to itself, meaning
id(𝑥)=𝑥 for all 𝑥 in the set

Question 4

What is the identity function on V(G)?

Answer 4

𝑖d⌄𝑉(𝐺) : V(G)→V(G)

id⌄(V(G)​)(v) = v

a vertex of G is inputed and the output is the same vertex

Question 5

What is injectivity?

Answer 5

A function is injective if no two elements from the domain are allowed to map to the same element in the codomain

Example:
a→1, b→2, c→3 is injective.
a→1, b→1 is not injective.

Question 6

What is surjectivity?

Answer 6

A function is surjective if every element in the target set is used at least once as an output.
Nothing in the target set is left out.

Example:
If the outputs are {1,2,3} and the target set is {1,2,3}, the function is surjective.
If 3 is never used, it is not surjective.

Question 7

What is bijectivity?

Answer 7

A function is bijective if it is both injective and surjective.
Every input has its own unique output, and every output is used exactly once.

Think: “Perfect matching” between the two sets.

Example:
a→1, b→2, c→3 is bijective.