# Edges between two parts of graph

Consider a (simple undirected) graph $G$ with set of vertices $V=A\cup B$ with $|B|=30$.

(1) Every vertex in $A$ has an edge to exactly $3$ vertices in $B$.

(2) Every vertex in $B$ has an edge to exactly $4$ other vertices in $B$.

(3) For any two vertices in $B$ connected by an edge, some vertex in $A$ is connected to both of them.

What is the minimum size of $A$?

--

The number of edges in $B$ is $2|B|=60$. The number of edges between $A$ and $B$ is $3|A|$. Condition (3) implies that for each of the $60$ edges in $B$, some vertex in $A$ is connected to both endpoints of the edge. Since every vertex in $A$ is connected to $3$ vertices in $B$ (hence also $3$ pairs of vertices), $|A|\geq 20$.

Is this the optimal bound, and if so, how can we construct an example?

Every vertex of $A$ covers 3 vertices of $B$, and at most covers 3 pairs of edges forming a triangle. So, to reach the lower bound of $|A|=20$, it suffices that $B$ is a $4$-regular in $30$ vertices such that its edges can be partitioned in triangles.
• I believe your graph is the $1$-skeleton of the icosidodecahedron (rectified dodecahedron), i.e., the solid obtained by taking a regular dodecahedron and cutting off each corner with a plane that passes through the midpoints of the three edges meeting at that corner. – bof Dec 17 '14 at 19:36
You are right, this is an optimal bound as shows the following example. The set $B$ consists of 5 copies of the following hexagonal graph. To each monochromatic triangle corresponds a vertex from the set $A$, connected with the vertices of the triangle.