연습문제를 풀다가 막혀서 드리는 질문이에요. 풀던 문제는 이렇습니다.

 

Let G and H are graphs. Prove the following

(2) If G⊆AxB and H⊆BxC then H○G⊆AxC

 

(x,y)∈H○G

⇔ ∃z s.t. (x,z)∈G ∧ (z,y)∈H (By the definition of composite graph H○G)

⇒ ∃z s.t. (x,z)∈AxB ∧ (z,y)∈BxC (∵ G⊆AxB and H⊆BxC)

⇔ ∃z s.t. (x∈A ∧ z∈B)∧(z∈B ∧ y∈C)

⇔ ∃z s.t. (x∈A ∧ y∈C)∧z∈B

⇔ ∃z s.t. ((x,y)∈AxC)∧z∈B

 

그런데 여기서 만약 B가 공집합이면 z가 존재하지 않아 (x,y)∈AxC 라고 할 수 없고, 따라서 H○G⊆AxC라고도 할 수 없는 게 아닌가요? 잘 모르겠습니다.