Recorrer un Grafo, usando arboles

Construir un programa en C que permita almacenar
un grafo (definido en forma rígida) y a partir de la selección de uno de los nodos,
defina árboles que representen los posibles caminos a recorrer.
Para ello, hacer lo siguiente:
a) Crear una estructura que permita almacenar el siguiente grafo:
b) Crear una estructura que permita almacenar un árbol, y los algoritmos de
recorrido de los árboles (inorder, preorden, postorden)
c) Crear un programa en C, que registre el grafo (inserte los 7 nodos y sus
correspondientes enlaces)
d) Que implemente en C el proceso de búsqueda por profundidad de caminos
posibles a partir de un nodo indicado por el usuario.
Por ejemplo, si el usuario dice 3, entonces los caminos posibles son:
3 – 5 – 4.
3 – 5 – 6
Si el usuario dice 4, los caminos son:
4- 6
2
4 – 3 – 5 – 6
Los caminos no están preprogramados, se debe recorrer el grafo.
E) Que el programa imprima los resultados del árbol en los distintos formatos:
inorden, preorden, postorden.

Por ultimo el codigo debe estar liberado para ser usado por cualquiera sin mencionar al creador.