No deberia dar problemas y no me los da. ¿Seguro que no estas haciendo absolutamente nada mas que genere el problema? Publica una version minima compilable que reproduzca el poblema o ejecuta tu programa bajo un depurador.

Pego el código completo -que llevo hasta ahora-, lo que pasa es que en buena parte es supérfluo, porque simplemente es el inicio de un código que espero llegue a mayor y lo que estoy haciendo es empezar a depurar antes de escribir más. Lo que me interesa es lo que pasa con respecto a num_nodos.
Lo del porqué los elementos [3][4] es simplemente para llevar un control, no es nada especial. También sé que se puede hacer con pila (push-pop) pero yo quiero hacerlo así, con un a rreglo hecho por mí.

	// Calcula si un grafo es conexo o no
#include <stdio.h>
#include <stdlib.h>
 
#define ORDEN_MATR num_nodos * num_nodos
 
void intro_grafo (int num_nodos, int ** matr_adher);
 
int main ()
{
	int num_nodos; // Nº de nodos del grafo
	int ** matr_adher; // Matriz de adherencia del grafo
	int nodo_actual; // El que se está procesando en un momento dado
	char * estado_nodo; // 1 - si ya se ha pasado por él al menos una vez; 0 - en caso contrario
	int * camino; // Guarda los nodos que se van recorriendo
	int posicion; // subindice del arreglo camino [] que corresponde a nodo_actual
	char sentido; // 1 si se va avanzando hacia nodo no visitado; 0 - si se va retrocediendo a nodo ya visitado
	int i, j;
 
	printf ("Introducir no. de nodos del grafo: ");
	scanf ("%d", &num_nodos);
	printf ("el numero es: %d\n", num_nodos);
		// Declara variables
		matr_adher = (int **) malloc ( ORDEN_MATR * sizeof (int *) ); // Filas
		for ( i=0; i < ORDEN_MATR; i++ )
		{
			matr_adher [i] = (int *) malloc ( num_nodos * sizeof (int) ); // Columnas
		}
		estado_nodo = (char *) malloc ( sizeof(num_nodos) );
		camino = (int *) malloc ( sizeof(num_nodos) );
 
			// Inicializa variables
		for (i = 0; i < ORDEN_MATR; i++)
			for (j = 0; j < ORDEN_MATR; j++)
				matr_adher [i][j] = 0; // Por defecto ningun nodo esta conectado con nigun otro
		for (i = 0; i < ORDEN_MATR; i++)
			estado_nodo [i] = 0; // Al inicio no se ha visitado ningun nodo
		sentido = 1;
 
	intro_grafo (num_nodos, matr_adher);
	printf ("elem %d, %d = %d\n", 3,4, matr_adher [3][4]);
	printf ("elem %d, %d = %d\n", 4,3, matr_adher [3][4]);
 
	return 0;
}
 
void intro_grafo (int num_nodos, int ** matr_adher)
{
	int nodo1, nodo2, peso;
 
	printf ("Introducir conexiones y pesos entre nodos en la forma:\n");
	printf ("nudo inicial... nudo final... peso conexion\n\n");
	printf ("No es necesario introducir coexiones reciprocas, la conexion i-j automaticamente es = a la j-i\n");
	printf ("Una nueva conexion i-j actualiza a la anterior si existiera\n");
	printf ("para finalizar el grafo introduzca nudo incial = 0 y nudo final = 0\n\n");
	for (;;)
	{
		printf ("Nodo inicial: ");
		scanf ("%d", &nodo1);
		printf ("Nodo final: ");
		scanf ("%d", &nodo2);
		if (nodo1 == 0 && nodo2 == 0)
			return;
		else
		{
			printf ("Peso conexion: ");
			scanf ("%d", &peso);
			matr_adher [nodo1][nodo2] = peso;
			matr_adher [nodo2][nodo1] = peso;
			printf ("\n");
		}
	}
}
 

Ejecución en entorno Windows a mano:
al introducir no. de nodos del grafo: 14 (>9); el programa se sale. 3 Primeras líneas de la imagen de ejecución. Al introducir: 14 el programa se sale, al introducir:4 el programa prosigue tal cual está estipulado.




Ejecución en entorno Windows -Visual Code-:
Se introducen no. nodos del grafo: 17 (>9)... el programa se sale. Se introducen 6:---> el programa sigue.




Ejejecución en entorno Windows, máquina virtual UbuntU:
se introducen no. nodos del gráfo:23 ---> el programa actúa como se espera de él.



Si queréis puedo ejecutarlo también en un Lubuntu como SO nativo -no en máquina virtual- (tengo también un Lubuntu en arranque dual) pero creo que no hace falta. Parece que se ve que se comportan distinto el código C en Windows y Linux.

NOTA: el código es el mismo en todos los casos: copiar y pegar. No hay la más mínima diferencia. Sólo entre los nombres de los ejecutables (con .exe en Windows y sin nada an Linux).

He probado a ejecutar tu código y tus mismos ejemplos en Windows (tanto desde CMD como Powershell) y... Funciona correctamente.

De todas formas, yo diría que el problema puede andar por las líneas 29 y 30. Utiliza:

estado_nodo = (char*)malloc(num_nodos * sizeof(char));
camino = (int*)malloc(num_nodos * sizeof(int)); 

Si eso no soluciona tu problema, muestra mensajes por pantalla entre las líneas de los cálculos para ver hasta qué línea se ejecuta exactamente.

---

Además de esto, otra cosa aparte: Cuando definas una macro compleja con #define, usa siempre paréntesis.

#define A 2 * 2
#define B (2 * 2)
 
int a = 16 / A; // a = 16 / 2 * 2 = 16
int b = 16 / B; // b = 16 / (2 * 2) = 4 

De nada; las lineas que te señalo K-YreX  tambien esta mal, estas usando sizeof de num_nodos que siempre sera lo mismo ...