in Graph Theory retagged by
856 views
0 votes
0 votes
If G is a connected k-regular graph with chromatic number k+1, then find the number of edges in G?
in Graph Theory retagged by
by
856 views

4 Comments

srestha yes the graph you told have chromatic number 3 which fits the theorem above because it consists odd cycle. 

0
0
2 x |E|  = k*N

 |E| = k*N/2

when N is odd
0
0
so basically just by knowing k+1 chromatic number and k-regular one cannot identify the number of edges?
because

2-regular graph with 3 vertices have chromatic number 3 and have 3 edges whereas

2-regular graph with 5 vertices have chromatic number 3 and have 5 edges

but if know the vertices then there can be a formula depending on the graph is complete or not complete and contains a odd cycle
2
2

Please log in or register to answer this question.

Related questions