We exactly evaluate the entanglement of a six vertex and a nine vertex graph states which correspond to non “two-colorable” graphs. The upper bound of entanglement for five vertex ring graph state is improved to 2.9275, less than the upper bound determined by local operations and classical communication. An upper bound of entanglement is proposed based on the definition of graph state. Author: Xiao-Yu Chen, College of Information and Electronic Engineering, Zhejiang Gongshang University, Hangzhou 310018, China