We work on an extension of the Population Protocol model of Angluin et al. that allows edges of the communication graph, G, to have states that belong to a constant size set. In this extension, the so called Mediated Population Protocol model (MPP), both uniformity and anonymity are preserved. We here study a simplified version of MPP, the Graph Decision Mediated Population Protocol model (GDM), in order to capture MPP's ability to decide (stably compute) graph languages (sets of communication graphs). To understand properties of the communication graph is an important step in almost any distributed system. We prove that any graph language is undecidable if we allow disconnected communication graphs. As a result, we focus on studying the computational limits of the GDM model in (at least) weakly connected communication graphs only and give several examples of decidable graph languages in this case. To do so, we also prove that the class of decidable graph languages is closed under complement, union and intersection operations. Node and edge parity, bounded out-degree by a constant, existence of a node with more incoming than outgoing neighbors and existence of some directed path of length at least k=O(1) are some examples of properties whose decidability is proven. To prove the decidability of graph languages we provide protocols (GDMs) for them and exploit the closure results. Finally, we prove the existence of symmetry in two specific communication (sub)graphs which we believe is the first step towards the proof of impossibility results in the GDM model. In particular, we prove that there exists no GDM, whose states eventually stabilize, to decide whether G contains some directed cycle of length 2 (2-cycle).