So, what does this set of possible outcomes look like if the r.v is a
graph structure and what does the r.v map it to?
Further, how do we assign probability to elements of the set of all
finite graphs ?
$\newcommand\B{\mathscr B}$Suppose that the set of vertices of each realization of the finite random graph $G$ is $[n]=\{1,\dots,n\}$ for some natural $n$. Let $S_n$ denote the set of all graphs with the vertex set $[n]$. Then all realizations of $G$ are in the set
$$S:=\bigcup_{n=1}^\infty S_n.$$
For each natural $n$, the set $S_n$ is finite and hence the set $S$ is countable.
Let $\B_n$ and $\B$ denote the powersets of $S_n$ and $S$, respectively. Let $P_n$ be any probability measure on $\B_n$; for instance, one can let $P_n$ be the uniform distribution over the set $S_n$. Take any sequence $(p_n)_{n=1}^\infty$ of nonnegative real numbers such that $\sum_{n=1}^\infty p_n=1$. Define the probability measure $P$ on $\B$ by the formula
$$P(A):=\sum_{n=1}^\infty p_n P_n(A\cap S_n) \tag{1}$$
for all $A\in\B$.
Then the random graph $G$ can be defined on the probability space $(S,\B,P)$ as the identity mapping of $S$ to itself ($G(g):=g$ for all graphs $g\in S$). Then
the distribution of the random graph $G$ will obviously be $P$.
Since any probability measure on $\B$ can be represented by (1), this way you can define a random graph with values in $S$ and any prescribed distribution over $S$ (that is, any prescribed distribution on the $\sigma$-algebra $\B$).
