The integration of graphene (Gr) with nitride semiconductors is highly interesting for applications in high-power/high-frequency electronics and optoelectronics. In this work, we demonstrated the direct growth of Gr on Al0.5Ga0.5N/sapphire templates by propane (C3H8) chemical vapor deposition (CVD) at temperature of 1350{deg}C. After optimization of the C3H8 flow rate, a uniform and conformal Gr coverage was achieved, which proved beneficial to prevent degradation of AlGaN morphology. X-ray photoemission spectroscopy (XPS) revealed Ga loss and partial oxidation of Al in the near-surface AlGaN region. Such chemical modification of a 2 nm thick AlGaN surface region was confirmed by cross-sectional scanning transmission electron microscopy (STEM) combined with electron energy loss spectroscopy (EELS), which also showed the presence of a bilayer of Gr with partial sp2/sp3 hybridization. Raman spectra indicated that the deposited Gr is nanocrystalline (with domain size 7 nm) and compressively strained. A Gr sheet resistance of 15.8 kOhm/sq was evaluated by four-point-probe measurements, consistently with the nanocrystalline nature of these films. Furthermore, nanoscale resolution current mapping by conductive atomic force microscopy (C-AFM) indicated local variations of the Gr carrier density at a mesoscopic scale, which can be ascribed to changes in the charge transfer from the substrate due to local oxidation of AlGaN or to the presence of Gr wrinkles.