Verbal Fluency Tests (VFT) are one of the most common neuropsychological tasks used in bipolar disorder (BD) and schizophrenia (SZ) research. Recently, a new VFT analysis method based on graph theory was developed. Interpreting spoken words as nodes and every temporal connection between consecutive words as edges, researchers created graph structures, allowing the extraction of more data from participants’ speech, called Speech Graph Attributes (SGA). The aim of our study was to compare speech graphs, derived from Phonemic and Semantic VFT, between SZ, BD, and healthy controls (HC). Twenty-nine SZ patients, twenty-nine BD patients, and twenty-nine HC performed Semantic and Phonemic VFT. Standard measures (SM) and 13 SGA were analyzed. SZ patients’ Semantic VFT graphs showed lower total word count and correct responses. Their graphs presented less nodes and edges, higher density, smaller diameter, average shortest path (ASP), and largest strongly connected component than the HC group. SM did not differentiate BD and HC groups, and patients’ Semantic VFT graphs presented smaller diameter and ASP than HC. None of the parameters differentiated BD and SZ patients. Our results encourage the use of speech graph analysis, as it reveals verbal fluency alterations that remained unnoticed in the routine comparisons of groups with the use SM.