Consider a pair of memoryless correlated sources $(X,Y)$. With the collection of strongly typical sequences (of length $n$) of $X$ and $Y$, one can associate a nearly semi-regular bipartite graph. The typical sequences of $X$ and $Y$ form vertices, and two sequences are connected by an edge if they are jointly typical. There are roughly $2^{nH(X)}+2^{nH(Y)}$ vertices and $2^{nH(X,Y)}$ edges in this graph. In this work, we study the structural properties of these graphs. In particular, we study regularity and sparcity of this graph by considering the asymptotic properties of random collection of samples (random subgraphs) taken from this graph. These results find applications in certain graph-based frameworks for transmission of correlated sources over multiuser channels.