Tagged Questions

Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.

27 views

Does this $G$ graph have an Euler path?

$G$ is a simple graph whose vertex set is $\{ 1, \ldots ,100\}$, vertices $i$ and $j$ are connected if $1 \le |i-j| \le 2$. Does an Euler path exist in $G$? I know that Euler’s Theorem 1 If a ...
29 views

From the mountain top to the coast.

From a mountain top lead to ways to the (sea)coast. Neither way goes below of the sea level or over of the mountain top. Show that Adam and Barbara can go on the roads from the mountain top to the sea ...
48 views

Right way of getting degrees of vertices

Suppose I have the following list of nodes: A E G A E H A F G A F H B E G B E H B F G B F H C F C E D G D H Every line indicates the connections between those nodes. So there is a connection ...
16 views

The modularity formula of Newmann and Girvan

I have question concerning the modularity formula of Michelle Girvan and Mark Newman. It says that it measures the fraction of edges in a network, that connects nodes, within the same ...
23 views

Euler's formula about graphs embedded in $\mathbb{R^2}$

State and prove Euler's formula about graphs embedded into $\mathbb{R^2}$ I know that if we suppose $G$ is a finite connected graph drawn on the surface of a sphere $S^2$. Then the ...
23 views

Directed Weighted Graph with no cycles - LP

I have directed weighted graph. I have to find a set of edges with minimal sum of their weights that without the set graph becomes acyclic. I can call lp solver multiple times. I'm kind off lost on ...
69 views

First scientific work. [closed]

One year ago I decided to myself to write my own scientific work in number theory, graph theory or combinatorics. I tried to find the teacher and theme during this year, but unfortunately I didn't ...
13 views
+50

Multi modal transport network and graph theory

I am attempting to model a multi layered transport graph with points that allow for travellers to laterally transfer between graphs, in order to make use of different transport nodes. Conceptually, ...
26 views

Graph theory notation misunderstanding

I know $K_n$ means the complete graph on n vertices. But in my lecture notes it said "Consider $2K_n$. Please could you tell me what this means?
106 views

18 views

3 regular graph, 10 vertices, non-adjacent vertices have common neighbour

How can I show the following: in any 3-regular graph with 10 vertices, every pair of non-adjacent vertices, has a common neighbour. I've seen on the internet that there are some very general proofs ...
23 views

Claim: In every graph with at least 2 vertices you can always find 2 vertices with the same degree

This appeared as an excercise in my problem sheet at uni. How can this be true for any graph? Ive added a pic of a graph which fails. I've put the degree above the vertex. I did this on powerpoint- ...
33 views

Is the Wikipedia article about chordal graphs incorrect?

This is the wiki for chordal graphs. It states that "A perfect elimination ordering in a graph is an ordering of the vertices of the graph such that, for each vertex v, v and the neighbors of v that ...
77 views

What is an intuition behind permanent?

I would like to know what is your intuition behind permanent of a matrix. For me, it looks like someone came and saw determinant, deleted permutation sign and voila, we have permanent and it counts ...
36 views

Graph with nine edges and all vertices of degree 3

There is a graph with nine edges and all vertices of degree 3? I don't think that this graph exist, but I don't know how to proof.