There are a couple of exercise in my lecture notes on graph theory to which I am unable to produce an answer for. Letting $X$ be the class of $(K_{1,3} ,K_{4})$-free graphs (graphs containing neither $K_{1,3}$ or $K_{4}$) and asks the following:
$\bullet$ Show that each $n$-vertex bipartite graph in $X$ has at most $n$ edges. Find an $n$-vertex bipartite graph in $X$ with $n$ edges.
$\bullet$ Show that each $n$-vertex comparability graph in $X$ has at most $2n$ edges. Find an $n$-vertex comparability graph in $X$ with $2n$ edges.
$\bullet$ Show that each $n$-vertex graph in $X$ has at most $\frac{5n}{2}$ edges. Find an $n$-vertex graph in $X$ with more than $2n$ edges.
For the first point concerning bipartite graphs I argued that each vertex may only have a maximum degree of $2$, else if it were more then this vertex and its $3$ neighbours would admit an induced $K_{1,3}$. Therefore for any bipartite graph $G$ in $X$, we would have $|E(G)| \leq \frac{2 \cdot n}{2}$ accounting for counting edges twice, producing the answer. An example of a graph with $n$ vertices would be any even cycle with $n \geq 4$ such as $C_{6}$.
For the second point I am completely unsure in which direction to approach the problem. I know that an indirected graph is a comparability graph if it admits a transitive orientation, but I am completely stuck on how to apply this. This exercise was in the section on Ramsey theory, so I was wondering if I needed to implement this for either of the last two problems.
Help appreciated as always, thanks!
A bipartite graph with no induced $K_{1,3}$ has maximum degree at most $2;$ if it has $n$ vertices then it has at most $n$ edges.
The bipartite graph $K_{2,2}=C_4\in X$ has $4$ vertices and $4$ edges.
A poset $P$ with no $4$-element chain is the union of $3$ antichains; namely, $P=A_1\cup A_2\cup A_3$ where the antichain $A_k$ consist of all elements $x\in P$ such that the longest chain with $x$ as its top element has length $k.$ In other words, a $K_4$-free comparability graph $G$ is $3$-colorable. If $G$ also has no induced $K_{1,3}$ then each vertex has at most $4$ neighbors, namely, two of each color different from its own. A graph with $n$ vertices and maximum degree $\le4$ has at most $2n$ edges. (More generally, by the same argument, an $n$-vertex perfect graph in $X$ has at most $2n$ edges.)
The complete tripartite graph $K_{2,2,2}$ belongs to $X;$ it is the comparability graph of the poset $\{2,3,12,18,72,108\}$ ordered by divisibility, and it has $6$ vertices and $12$ edges.
Using the Ramsey number $R(3,3)=6,$ it's easy to see that a graph in $X$ has maximum degree $\le5;$ therefore, if it has $n$ vertices, it has at most $\frac{5n}2$ edges.
The Schlegel diagram of an icosahedron (dual of a dodecahedron) has $12$ vertices and $30$ edges and belongs to $X.$