Prove that simple graph $G$ is orientable

Question

I am a student in an introductory class for graph theory and this question is on our first homework assignment and I don't know where to start to prove the following:

Suppose that $n \geq 3$ and a simple graph G has $n$ vertices and at least $(n^2 - 3n + 6)/2$ edges. Prove that G is orientable.

Thank you for your time. Any hints or help will be greatly appreciated.

EDIT: A graph g is orientable if it is the underlying graph of a strongly connected digraph. A digraph is strongly connected if for all vertices $v$ and $w$ there exists a walk $v-w$.

Answer 1

First thing which come to my mind is to suppose that this is non-orientable graph.

So if we suppose that this is non-orientable, then it follows to 2 cases (maybe more):

1) It is a path graph. 2) It has a bridges in it (so cycles, as well).

What is the number of edges it should have, if it is a path graph? What if it has bridges+cycles?

Keep in mind it is simple graph, so no loops and multiple edges.

Answer 2

A few hints in addition to @Birch_SL.

How many edges does a complete graph have? How close is that to the number of edges your graph has?

If the graph isn't orientable, what does that mean?

We can try to tease out the structure that Birch_SL is assuming to exist. Namely, in any given orientation, there is a vertex $v$ that has no path to some $w$. Consider the set of all vertices accessible from $v$ and the set of those not. What do the edges between these sets look like? Could you come up with another orientation that is strongly connected (be careful here)?

Finally,

What's the only way to not come up with an orientation that isn't strongly connected? How many edges must be missing?

Answer 3

Let's assume that given graph (with the bunch of properties) is non-orientable, with more than or equal to 3 vertices.

As we know, from one of the definitons, stated in class, is that the simple graph G is not orientable, if it contains a bridge.

Now, let's construct such a graph:

Let's take for our proof simple graph, which contains two 3-vertex cycles, joined by one bridge. That graph has no problems with properties stated in the givens.

So the number of edges is $$m=m_1+m_2+1=n_1+n_2+1=3+3+1=7$$, such that $m_1,m_2,n_1,n_2$ are number of edges of first cycle,--||--||--of second cycle, number of vertices of first cycle and second, respectively.

Now, lets plug in total amount of vertices (6) into the formulae, which is in the given.

$$m={n^2−3n+6\over 2}=24/2=12$$

Since the number of edges of our non-orientable graph is less than calculated by formulae, so our statement that simple graph with $n\geq 3$ vertices has bridges => It is false statement, that simple graph with $n\geq 3$ vertices is non-orientable.

Therefore the graph with such properties is orientable.

---

---

Feel free to comment my proof, if you have better ideas.

Answer 4

By Robin's Theorem, a graph is orientable if and only if it is connected and has no bridge.

So try to prove:

Step 1: Any graphs with $(n^2 - 3n + 6)/2$ edges is connected.

Step 2: Any graphs with $(n^2 - 3n + 6)/2$ edges cannot have bridges.

Step 1 is pretty standard and easy. For step 2, assume by contradiction that $G$ has a bridge $b$ then, by erasing this bridge you get a graph with two disjoint components, one with $k$ vertices and the other one with $n-k$ vertices.

What is the maximum number of vertices in each component?