edited by
447 views
5 votes
5 votes
Let $\text{G}$ be the following set of undirected connected graphs $:$

$\text{G} = \{ g \mid g \;\text{is a complete graph on}\; n\; \text{vertices where}\; 1\leq n \leq 10 \;\text{OR} \;g$ is a cycle graph on $n \;\text{vertices where}\; 3\leq n \leq 10 \}$

On set $\text{G},$ we define a relation $\text{R}$ as following $:a\text{R}b$ if and only if $a$ is isomorphic to $b.$

How many equivalence classes will be there for $\text{R}?$
edited by

1 Answer

8 votes
8 votes
Isomorphism of simple graphs is an equivalence relation.

Any graph is Isomorphic to itself so Reflexive.

If $\text{G}$ Isomorphic to $\text{H}$ then $\text{H}$ Isomorphic to $\text{G}$ so Symmetric. And if $\text{G}$ Isomorphic to $\text{H}$ and $\text{H}$ Isomorphic to $\text{I}$ then $\text{G}$ Isomorphic to $\text{I},$ so transitive.

So, isomorphism of simple graphs is an equivalence relation.

There will be $17$ equivalence classes for $\text{R}.$

The equivalence class will be $\text{K1}$ to $\text{K10}$ and $\text{C4}$ to $\text{C10}.$ Note that $\text{C3}$ is in same equivalence class of $\text{K3}.$
Answer:

Related questions