Losing the first element of a pointer due to bad memory allocations (i think)

Question

First of all, sorry for the long code block. This is my current project where I need to manipulate graphs that simulate routes between locations. However, when I try to add a new node to the graph, it seems like all of the links from a certain node to node 0 ("Amsterdam") are lost. Here is the code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "functions.h"

#define MAX_CHAR 100

struct node
{
    char name[MAX_CHAR];
    struct edge *connections;
    int numConnections;
};

struct edge
{
    struct node *destination;
    int days;
};

struct graph
{
    struct node *nodes;
    int num_nodes;
};

struct ship
{
    char name[MAX_CHAR];
    struct cargo *cargo;
    char departure[MAX_CHAR];
    char destination[MAX_CHAR];
    float max_cargo;
};

struct cargo
{
    char name[MAX_CHAR];
    float weight;
    float value;
};

/* Function that checks for any memory allocation */
void check_allocation(const void *ptr, char function[MAX_CHAR])
{
    if (!ptr)
    {
        printf("%s: Error allocating memory", function);
        exit(1);
    }
}

Graph *create_graph(int numNodes)
{
    int i;

    Graph *graph = (Graph *)malloc(sizeof(Graph));
    check_allocation(graph, "create_graph");

    graph->num_nodes = numNodes;

    graph->nodes = (Node *)malloc(numNodes * sizeof(Node));
    check_allocation(graph->nodes, "create_graph");

    for (i = 0; i < numNodes; i++)
    {
        strcpy(graph->nodes[i].name, "");
        graph->nodes[i].numConnections = 0;
        graph->nodes[i].connections = NULL;
    }
    return graph;
}

void add_node(Graph *graph, char name[MAX_CHAR])
{
    graph->num_nodes += 1;
    Node *temp = (Node *)realloc(graph->nodes, graph->num_nodes * sizeof(Node));
    check_allocation(temp, "add_node");
    graph->nodes = temp;

    strcpy(graph->nodes[graph->num_nodes - 1].name, name);
    graph->nodes[graph->num_nodes - 1].numConnections = 0;
    graph->nodes[graph->num_nodes - 1].connections = NULL;
}

void add_edge(Node *v1, Node *v2, int days)
{
    v1->numConnections += 1;
    v2->numConnections += 1;

    Edge *temp1 = (Edge *)realloc(v1->connections, v1->numConnections * sizeof(Edge));
    check_allocation(temp1, "add_edge");
    v1->connections = temp1;

    Edge *temp2 = (Edge *)realloc(v2->connections, v2->numConnections * sizeof(Edge));
    check_allocation(temp2, "add_edge");
    v2->connections = temp2;

    v1->connections[v1->numConnections - 1].destination = v2;
    v1->connections[v1->numConnections - 1].days = days;
    v2->connections[v2->numConnections - 1].destination = v1;
    v2->connections[v2->numConnections - 1].days = days;
}

Graph *create_initial_routes()
{
    /* Allocate memory for the graph */
    Graph *routes = create_graph(9);
    check_allocation(routes, "create_initial_routes");

    strcpy(routes->nodes[0].name, "Amsterdam");
    strcpy(routes->nodes[1].name, "Hamburg");
    strcpy(routes->nodes[2].name, "Izmit");
    strcpy(routes->nodes[3].name, "Botas");
    strcpy(routes->nodes[4].name, "Marseille");
    strcpy(routes->nodes[5].name, "Valencia");
    strcpy(routes->nodes[6].name, "Algeciras");
    strcpy(routes->nodes[7].name, "Le Havre");
    strcpy(routes->nodes[8].name, "Antwerp");

    add_edge(&routes->nodes[0], &routes->nodes[1], 1);
    add_edge(&routes->nodes[0], &routes->nodes[2], 6);
    add_edge(&routes->nodes[1], &routes->nodes[2], 6);
    add_edge(&routes->nodes[2], &routes->nodes[3], 3);
    add_edge(&routes->nodes[2], &routes->nodes[4], 7);
    add_edge(&routes->nodes[4], &routes->nodes[5], 3);
    add_edge(&routes->nodes[4], &routes->nodes[8], 3);
    add_edge(&routes->nodes[5], &routes->nodes[6], 3);
    add_edge(&routes->nodes[6], &routes->nodes[7], 4);
    add_edge(&routes->nodes[7], &routes->nodes[8], 1);

    return routes;
}

void show_routes(Graph *graph)
{
    int i, j;
    for (i = 0; i < graph->num_nodes; i++)
    {
        printf("%s\n", graph->nodes[i].name);
        for (j = 0; j < graph->nodes[i].numConnections; j++)
            printf("Connection %d: %s\n", j + 1, graph->nodes[i].connections[j].destination->name);
    }
}

int check_existence(Graph *graph, char name[MAX_CHAR])
{
    int i;
    for (i = 0; i < graph->num_nodes; i++)
        if (strcmp(graph->nodes[i].name, name) == 0)
            return 1;
    return 0;
}

void add_port(Graph *graph, char name[MAX_CHAR], char *connections[MAX_CHAR], int numConnections)
{
    printf("-----------------\n");
    int i, j;
    if (!check_existence(graph, name))
    {
        add_node(graph, name);

        for (i = 0; i < graph->num_nodes; i++)
            for (j = 0; j < numConnections; j++)
                if (strcmp(graph->nodes[i].name, connections[j]) == 0)
                    add_edge(&graph->nodes[graph->num_nodes - 1], &graph->nodes[i], 10);
    }
}

void free_memory(Graph *graph)
{
    int i;
    for (i = 0; i < graph->num_nodes; i++)
        free(graph->nodes[i].connections);

    free(graph->nodes);
    free(graph);
}

Before adding the node, this is what I get:

Amsterdam: Connection 1: Hamburg, Connection 2: Izmit

Hamburg: Connection 1: Amsterdam, Connection 2: Izmit

Izmit: Connection 1: Amsterdam, Connection 2: Hamburg, Connection 3: Botas, Connection 4: Marseille

Botas: Connection 1: Izmit

Marseille: Connection 1: Izmit, Connection 2: Valencia, Connection 3: Antwerp

Valencia: Connection 1: Marseille, Connection 2: Algeciras

Algeciras: Connection 1: Valencia, Connection 2: Le Havre

Le Havre: Connection 1: Algeciras, Connection 2: Antwerp

Antwerp: Connection 1: Marseille, Connection 2: Le Havre

---

After I add the node, this is what I get:

---

Amsterdam: Connection 1: Hamburg, Connection 2: Izmit

Hamburg: Connection 1: ÿ↑©, Connection 2: Izmit

Izmit: Connection 1: ÿ↑©, Connection 2: Hamburg, Connection 3: Botas, Connection 4: Marseille

Botas: Connection 1: Izmit,

Marseille: Connection 1: Izmit, Connection 2: Valencia, Connection 3: Antwerp

Valencia: Connection 1: Marseille, Connection 2: Algeciras, Connection 3: Lisbon

Algeciras: Connection 1: Valencia, Connection 2: Le Havre, Connection 3: Lisbon

Le Havre: Connection 1: Algeciras, Connection 2: Antwerp

Antwerp: Connection 1: Marseille, Connection 2: Le Havre

Lisbon: Connection 1: Valencia, Connection 2: Algeciras

The connection between hamburg and amsterdam, as well as between izmit and amsterdam is lost due to, I would guess, bad memory allocation. However, I can't find what is wrong when I allocate memory for my structs

I have tried allocating the memory before I increment the node numbers or the edge numbers, making sure I'm allocating the correct amount of memory by adding +1 to the new memory block size. However, this did not work as well