No, this type of record association should not result in an SOQL query.

I've executed this simple code snippet in the dev console to demonstrate:

Case cs = new Case();
cs.Subject = 'test external id';
cs.Description = 'sfsdgdfgfdh';
cs.Contact = new Contact(External_CRM_Id__c = '12345');
insert cs;

and in the logs we get this

17:38:39.645 (4645087977)|LIMIT_USAGE_FOR_NS|(default)|
  Number of SOQL queries: 0 out of 100
  Number of query rows: 0 out of 50000
  Number of SOSL queries: 0 out of 20
  Number of DML statements: 1 out of 150
  Number of Publish Immediate DML: 0 out of 150
  Number of DML rows: 1 out of 10000
  Maximum CPU time: 54 out of 10000

So no SOQL query was executed (this is with all triggers and flows turned off). If you're hitting limits, most likely other automations are to blame.

Flows and apex do not necessarily correspond in behaviour, so it's better to rely on documentation specifically for apex (or - in case it's lacking - to give it a try in the dev console).

No, this type of record association should not result in an SOQL query.

I've executed this simple code snippet in the dev console to demonstrate:

Case cs = new Case();
cs.Subject = 'test external id';
cs.Description = 'sfsdgdfgfdh';
cs.Contact = new Contact(External_Id__c = '12345');
insert cs;

and in the logs we get this

17:38:39.645 (4645087977)|LIMIT_USAGE_FOR_NS|(default)|
  Number of SOQL queries: 0 out of 100
  Number of query rows: 0 out of 50000
  Number of SOSL queries: 0 out of 20
  Number of DML statements: 1 out of 150
  Number of Publish Immediate DML: 0 out of 150
  Number of DML rows: 1 out of 10000
  Maximum CPU time: 54 out of 10000

So no SOQL query was executed (this is with all triggers and flows turned off). If you're hitting limits, most likely other automations are to blame.

Flows and apex do not necessarily correspond in behaviour, so it's better to rely on documentation specifically for apex (or - in case it's lacking - to give it a try in the dev console).