How to properly design this part of a database (ci

Situation:

A company has many projects
A project has many tags

A project belongs to only 1 company
A tag can belong to multiple projects

A company must have access to its own tags

Example 1:

In the first image, all tags for the company are available through the projects/project_tag. But if all projects are removed, then the tags for the company will not be accessible anymore, because the link between project_tag and projects is gone. The tags should be somehow always be linked to the company, even if there are no projects.

Example 2 (where tags are also linked to the company):

In the second image, it should work, but is this now a 'circular reference' ??? What should be the best solution for a problem like this? And what about foreign keys?

The question finally is: How to properly set up a database/datamodel for this situation?

Example when things could go wrong in the second example:

companies:
id=1, name=MyCompany
id=2, name=OtherCompany

tags:
id=1, company_id=1, name=MyTag
id=2, company_id=2, name=OtherTag

projects:
id=1, company_id=1, name=MyProject

project_tag:
project_id=1, tag_id=1
project_id=1, tag_id=2 --> THIS ROW IS NOT VALID!

The last project_tag row is not valid because:
project 1 is linked to company_id 1
tag_id 2 is linked to company_id 2

UPDATED: Thanks all for the information!

Based on the accepted answer, the CREATE queries for PostgreSQL would become:

CREATE TABLE companies (
   id SERIAL PRIMARY KEY NOT NULL,
   name TEXT NOT NULL
);
CREATE TABLE projects (
   id SERIAL PRIMARY KEY NOT NULL,
   company_id INT NOT NULL,
   name TEXT NOT NULL,
   UNIQUE (id, company_id),
   FOREIGN KEY (company_id) REFERENCES companies (id) ON DELETE RESTRICT ON UPDATE CASCADE
);
CREATE TABLE tags (
   id SERIAL PRIMARY KEY NOT NULL,
   company_id INT NOT NULL,
   name TEXT NOT NULL,
   UNIQUE (id, company_id),
   FOREIGN KEY (company_id) REFERENCES companies (id) ON DELETE CASCADE ON UPDATE CASCADE
);
CREATE TABLE project_tag (
   id SERIAL PRIMARY KEY NOT NULL,
   company_id INT NOT NULL,
   project_id INT NOT NULL,
   tag_id INT NOT NULL,
   UNIQUE (company_id, project_id, tag_id),
   FOREIGN KEY (company_id, project_id) REFERENCES projects (company_id, id) ON DELETE CASCADE ON UPDATE CASCADE,
   FOREIGN KEY (company_id, tag_id) REFERENCES tags (company_id, id) ON DELETE CASCADE ON UPDATE CASCADE
);

Tested:
- Rows inserted in project_tag are checked on the same company_id (else: denied)
- Not possible to insert duplicate rows into project_tag
- If a project is removed, the linked project_tag rows are also removed
- If a tag is removed, the linked project_tag rows are also removed
- If a company is being removed while still having projects, the removal is rejected (see projects table: ON DELETE RESTRICT)
- If a company (without projects) is removed, all linked tags are removed also

First of all, your second model is absolutely correct and there is not any circular reference in it.

You should transmit Company_ID of Company as F.K to Tags and Project and make it Not Null.

Then, you should transmit TAG_ID and Project_ID as F.Ks into Project_Tag and make the unique together. And there is no need to transmit the Company_ID of Project and Tag (that we transmitted in previous paragraph) into Project_Tag.

Now, how about final question, Your final request:

THIS ROW IS NOT VALID!

You can not capture it by ER. You should write some functions, triggers or stored procedures to capture and control it.

Edit:
Based on @reaanb's comments and his great answer here: You can control this constraint by this way with a little redundancy:

CREATE TABLE Project(
    project_id INT NOT NULL,
    company_id INT NOT NULL,
    PRIMARY KEY (project_id),
    FOREIGN KEY (company_id) REFERENCES Company (id),
    UNIQUE KEY (project_id, company_id)
);

CREATE TABLE Tag(
    tag_id INT NOT NULL,
    company_id INT NOT NULL,
    PRIMARY KEY (tag_id),
    FOREIGN KEY (company_id) REFERENCES Company (id),
    UNIQUE KEY (tag_id, company_id)
);

CREATE TABLE Project_Tags(
    id INT NOT NULL,
    company_id INT NOT NULL,
    project_id INT NOT NULL,
    tag_id INT NOT NULL,

    PRIMARY KEY (id),
    UNIQUE KEY (tag_id, project_id)

    FOREIGN KEY (project_id, company_id) REFERENCES Project (project_id, company_id),
    FOREIGN KEY (tag_id, company_id) REFERENCES Tag (tag_id, company_id),
);