A connection between graphs and categories that most introduction book would mention is the free-forgetful adjunction $$(F\colon Graph \rightarrow Cat ) \dashv (U\colon Cat \rightarrow Graph)$$ between categories:
- $Graph$ of small directed graphs and graph homomorphisms
- $Cat$ of small categories and functors
To spell this out naively just the action on objects of $F$ and $U$:
- $F$ takes given graph $g$ and give out the Free category $F(g)$ having as objects the same set of vertices in $g$ and as morphisms the directed paths in $g$. Morphism composition is the concatenation of paths and the identity morphism is the empty paths.
- $U$ takes a category $C$ and gives out the Underlying category $U(C)$ having as vertices the objects in $C$ and as directed edges the morphisms in $C$. The action of $U$ is intuitively to forget that there was composition and identity and extra properties that $C$ used to have.
I think even beginners (who don't yet understand adjunction) could appreciate why $F$ and $U$ is useful because whenever a book describe a "tiny" category by means of drawing a diagram such as
$$A \rightarrow B \rightarrow C$$$$\bullet \rightarrow \bullet \rightarrow \bullet$$
and say that it omits the identity anad transitive morphisms. What category it is describing is exactly the free category generated by the above directed graph.
I have a feeling that you are misunderstanding something as you mentioned
... represented on a subset of a complete graph of N vertices (Kn) which is connected. and partly directed? ...
I think what you mean is by representing a category $C$ with a graph is $U(C)$. And if that is the case, you would be wrong to say that $U(C)$ has to be "connected and partly directed". The underlying graph of a category doesn't have to be connected. Take for example, a category with just two objects and 2 identity morphisms.
A better description properties of $U(C)$ might be "transitive and reflective".