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? Graph Theory graph-theory graph-coloring + – dan31 asked Nov 6, 2018 retagged Jul 10, 2019 by Cristine dan31 1.2k views answer comment Share Follow See all 9 Comments See all 9 9 Comments reply Show 6 previous comments Mk Utkarsh commented Nov 6, 2018 reply Follow Share srestha yes the graph you told have chromatic number 3 which fits the theorem above because it consists odd cycle. 0 votes 0 votes Magma commented Nov 6, 2018 reply Follow Share 2 x |E| = k*N |E| = k*N/2 when N is odd 0 votes 0 votes Mk Utkarsh commented Nov 6, 2018 reply Follow Share 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 votes 2 votes Please log in or register to add a comment.