Determine whether G is bipartite graph and whether G is connected graph

64 Views Asked by At

Let $G = \langle V, E\rangle$ where $V = \mathbb{Z}_{100}$ and $E = \{\langle a, b\rangle : a \neq b \text{ and } a\text{ is a prime factor of }b\}$.

First I got $\mathbb{Z}_{100} = \{(0),(1), (2),(3),\ldots, (99)\}$, $|V|=100$ whereas |E| = let b=32, a=2 a not eq b 2 not eq 32 , E ={(2),(32)} (not sure if correct)

then notice that (a,0)=a for every a hence 0 is an isolated vertex.

till that, i can't think more, any explanation guys :'( need to understand more, few weeks left for final

1

There are 1 best solutions below

1
On

The nodes in the graph are all the integers 0...99.

Based on the definition of $E$, the edges of the graph connect prime numbers like 2,3,5,7,11,13 , ... to their larger multiples. For example, 2 is connected to 4, 6, 8, 10, ... . Node 3 is connected to 6, 9, 12, 15, 18, ... . Every prime number $p$ is connected to the composite numbers that have $p$ as a factor: 2p, 3p, 4p, 5p, ....

Yes, bipartite. Because prime numbers are only connected to composite numbers, this graph is bipartite. You can put all the prime numbers on one side and all the composites on the other side, and the edges form a bridge between them.

This graph looks at least mostly connected. For any two numbers $A$ and $B$, let $p$ and $q$ be one of their prime factors, respectively. Then $A$ is connected to $p$ is connected to $pq$ is connected to $q$ is connected to $B$.

The question is what to do about $0\in \mathbb{Z}_{100}$. Normally, for $\mathbb{Z}$, 0 would have nothing connected to it because 0 isn't prime, and 0 isn't a multiple of anything. But in $\mathbb{Z}_{100}$, 0 is a multiple of some things. For example, 5 * 20 = 100 $\equiv 0 \pmod{100}$. In $\mathbb{Z}_{100}$, every prime factor of 100 is a prime factor of 0, because $100 \equiv 0\pmod{100}$.

So 2 and 5 are prime factors of $0\pmod{100}$, and so 0 is connected to everything else, too.