Show, that if the removal of a vertex $v$ reduces the depth of a minimal acyclic orientation, every longest path contains $v$ Let $G = (V, E)$ be a graph, that contains directed and undirected edges.
$G$ has the following properties:

*

*let $(v_1, \dots, v_k)$ be a directed Path form $v_1$ to $v_k$,
then ther exists a directed edge $(v_1, v_k) \in E$

*it follows, that the nodes of ever directed path form a clique

*Only edges that are directed in $G$ have the transitive property

*$G$ is a perfect graph

*$G$ is acyclic
Now, let $H_G$ be a minimal acyclic orientation of $G$ so that.

*

*the length of the longest path is minimal

*every path of length $j$ cannot be shortened without creating a new path of at least length $j$
Shortening of a path: Let $p$ be a path in an acyclic Orientation $H_G$ of $G$.
If follows, that p is directed in $H_G$. If $p$ contains an edge that is undirected in $G$, we could flip the orientation of said edge in $H_G$, and cut/shorten the path at this edge. However, this does not always work, as it is possible to create a new and even longer path.
I want to prove the following statement:
If the longste path in $H_G$ contains at least $k$ vertices and
there exists a vertex $v \in E(G)$, so that the longest path in a minimal Orientation of the graph
$G' = G[V \setminus \{v\}]$ contains less than $k$ vertices, then every path of length $k$ in $H_G$ contains v.
 A: EDIT : The setup changed, this is no longer correct
Mixing directed and undirected edges is generally strange. And here, it turns out it doesn't really make sense.
First, your conditions imply that the graph is acyclic and transitive ($u \to v \wedge v \to w \Rightarrow u \to w$) so the undirected edges are all independent (no vertex is contained in two undirected edges).
Then, if two vertices are connected by an undirected edge ($u \leftrightarrow v$), then for every other vertex $w$, we have $u \to w \Leftrightarrow v \to w$ and $w \to u \Leftrightarrow w \to v$. The two vertices are indistinguishable, which means that if we swap $u$ and $v$, we get the same graph up to isomorphism.
Thus, all the orientations of the unoriented edges are isomorphic to each other. So, for every point of view, it doesn't matter which orientation you choose -- apart from one point of view, which is the labeling of the vertices that are part of an undirected edge.
For clarity, if $u \leftrightarrow v$ in $G$, I will write $s(u) = v$ and $s(v) = u$ : $s$ is the swapping function.
Now, the initial question becomes rather easy, because we don't have to worry about which orientation is minimal -- they're all the same, apart maybe from the position of the vertex $v$ that you're trying to remove.
But since this vertex $u$ is indistinguishable from its counterpart $s(u)$ in $G$, the only way to tell them apart is the orientation of the edge $u \leftrightarrow s(u)$. When you remove either $u$ or $s(u)$, this way to tell them apart disappear. So $H_G \setminus \{u\}$ is isomorphic to $H_G \setminus \{s(u)\}$, whatever orientation we choose for $H_G$. So all orientations are really the same for your problems.
Now, forget the ambiguity of the choice of orientation, and fix any orientation. You're asking to prove that, if removing a vertex forbids the existence of a path of length $k$, then this vertex is part of every path of length $k$. This seems rather straightforward, no ?
