Large language models (LLMs) with reasoning capabilities have shown impressive performance in clinical applications, yet the readability and traceability of their reasoning processes remain limited, as reasoning quality is often overlooked during training. To address this, we propose MedCEG, a framework that augments medical language models with clinically traceable reasoning by explicitly supervising the reasoning process through a critical evidence graph (CEG). Specifically, we curate challenging clinical cases and algorithmically construct a CEG for each sample via multi-model consensus as a high-quality, traceable reasoning pathway. The CEG reformulates the reasoning process for supervised fine-tuning and underpins a traceable reasoning procedure reward that evaluates generated reasoning against the CEG through deterministic graph operations measuring semantic matching, triplet recall and connected-component analysis. Experiments show that MedCEG surpasses existing methods among open-source medical models of comparable scale while producing clinically readable and traceable reasoning chains. Code and models are available at https://github.com/LinjieMu/MedCEG.