Retinal images play vital role in several applications such as disease diagnosis and human recognition. They also play a major role in early detection of diabetics by comparing the states of the retinal blood vessels. This paper presents an automatic approach for Artery/Vein classification based on the analysis of a graph extracted from the retinal vasculature. The graph extracted from the segmented retinal vasculature is analyzed to decide on the type of intersection points (graph nodes), and afterwards one of two labels is assigned to each vessel segment (graph links). Final classification of a vessel segment as A/V is performed through the combination of the graph-based labeling results with a set of intensity features.