2
$\begingroup$

The problem states that:

A simple (or strict) graph with $n$ vertices and $m>\dfrac{3(n-1)}{2}$ edges, has two vertex joined by three independent paths.

Any hints, ideas or useful results, to attack this problem?

$\endgroup$
2
  • $\begingroup$ Are the edges undirected? $\endgroup$
    – iamwhoiam
    Commented Nov 3, 2017 at 11:51
  • $\begingroup$ Yes, the graph is undirected $\endgroup$
    – plr
    Commented Nov 3, 2017 at 11:53

1 Answer 1

4
$\begingroup$

Here's a key lemma which by itself may help you get started.

Lemma. Any graph with $n$ vertices and $m > \frac32 (n-1)$ edges either:

Proof. Suppose the graph is not $2$-connected. Then there is a vertex $v$ such that the removal of $v$ leaves the graph disconnected. This means that we can partition the vertex set of the graph into a disjoint union $A \cup B \cup \{v\}$ (with $A,B \ne \varnothing$) such that there are no edges between $A$ and $B$.

If $A \cup \{v\}$ spans more than $\frac32 |A|$ edges, then it induces the subgraph we want. If $B \cup \{v\}$ spans more than $\frac32|B|$ edges, then it induces the subgraph we want. One of these has to happen: otherwise, the graph would contain at most $\frac32|A|+\frac32|B| = \frac32(n-1)$ edges, which violates the conditions of the lemma. $\square$


By the way, both the lemma and the result you want to prove are tight. When $m = \frac32(n-1)$, we have an infinite family of counterexamples known as the friendship graphs (shown below). If you don't read past the nice image taken from Wikipedia, you can still figure out the rest of the proof by yourself.

Frienship graph

If you do read on, then here's the rest of the solution.

The lemma lets us assume that the graph is $2$-connected. If not, we can keep passing to a smaller subgraph which satisfies the edge condition. But that can't keep happening forever, since $m > \frac32(n-1)$ means $\binom n2 > \frac32(n-1)$ which implies $n>3$. So eventually we end up in the first case of the lemma: at a subgraph which satisfies the edge condition and is $2$-connected.

Having $m > \frac32 (n-1)$ means $m>n$. This means the graph contains a cycle, which we'll call $C$.

If $C$ passes through all $n$ vertices, there must also be a non-cycle edge $vw$ (since there are more edges than just the $n$ edges along $C$). Now there are three independent paths from $v$ to $w$: by going clockwise around $C$, by going counterclockwise around $C$, and by the edge $vw$.

If $C$ passes through fewer than $n$ vertices, then (because the graph is connected) there must be a vertex $v$ with a neighbor $w$ outside $C$. Because the graph is $2$-connected, removing $v$ leaves a connected graph, so there must be a way to get from $w$ to $C$ not through $v$. Say the other path from $w$ to $C$ ends at a vertex $x$ of $C$. Then there are three independent paths from $v$ to $x$: by going clockwise around $C$, by going counterclockwise around $C$, and by going through $w$.

$\endgroup$
2
  • $\begingroup$ Does this lemma appear in a graph theory book? I've looked on Diestel's but did not find it. Can the lemma also be proved using the Global Version of Menger's Theorem? $\endgroup$
    – user
    Commented Mar 23, 2021 at 16:07
  • 1
    $\begingroup$ The lemma seems far too specific to appear in a textbook, though I wouldn't be surprised if it were an exercise somewhere. The general idea of "pass to a subgraph which maximizes some density-related parameter" certainly appears in textbooks. $\endgroup$ Commented Mar 23, 2021 at 16:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .