Bipartite graph

Question

The number of ways to properly color (using just sufficient colors) a connected graph without any cycle using five colors, such a way that no two adjacent nodes have the same color?

Comments

can you explain the question I not understand?

---

As we know that  connected Bipartite  graphs are 2 chromatic

---

connected graph without cycle means it is tree.

Every tree is a bi-pertite graph ===> 2 colors are needed to color them

we have 5 colors ===> ⁵P₂ = $\frac{120}{6}$ = 20.

Why ⁵P₂ , why not ⁵C₂ ?

because there is a difference between Partitions..., i mean partitions are numbered.

 

@Magma

complete bi-pertite is should have cycles when (every pertite contains more than one element )

Answer 1

I don't think the question is incomplete they are saying connected graph without cycle which means its a tree which is a bipartite graph! so no need to mention it explicitly.

Every tree we can divide into two groups such that no two vertices in a group share an edge. Suppose we have done that and we have two groups-A and B.

Now, from 5 colors we can select 2 different colors in 5C2 ways. Suppose we selected RED and BLUE.

we have two ways to assign R and B to these 2 groups. A-Red B-blue and A-Blue B-Red.

Total 5C2*2=20 ways.

Comments

 connected graph without cycle which means its a tree which is a bipartite graph

But a bipartite graph contains even cycles.
https://www.math.hmc.edu/~kindred/cuc-only/math104/lectures/lect03.pdf

---

do all bipartite graphs contain even cycles??

---

yes, all bipartite graph contains even cycle. you can see this one for proof-

https://www.whitman.edu/mathematics/cgt_online/book/section05.04.html

---

it is not necessary that a bipartite graph contain the even cycle 

take an example : full binary tree of 3 node (1 is root 2 is leaf) it is a bipartite but does not contain cycle

now correct statement is if there is a cycle in bipartite graph it should be even length