# 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.

Using this condition, doodling a bit in a piece of paper we reach this graph: It can be covered by 10 edge-disjoint triangles. It's not 4-regular, but taking two disjoint copies and identifying the vertex of degree 2 we reach a graph with the desired conditions.

• 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, 2014 at 19:36
• @bof Thanks! I was wondering if it there was a name for this construction. Of course, it depends on how you identify the vertices; you could join the "same" vertices of degree 2 in both copies and obtain a graph with induced cycles of size 6, which is not isomorphic to the graph you mention. Dec 17, 2014 at 19:46

It seems the following.

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. 