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.

learn more… | top users | synonyms

0
votes
1answer
6 views

Set of finite graphs with R: “is a sub-graph of” is a POSET

The question is: Show that the set of finite graphs with $R$: "is a sub-graph of" is a POSET I know a POSET is a set with a reflexive/anti-symmetric/transitive relation, but how can I show such a ...
1
vote
1answer
20 views

Approach to determining if a graph is planar by inspection/kuratowski's theorem

I'm taking an intro discrete math course and am having trouble determining if a graph is planar or not. When proving a graph is planar, if Euler's formula doesn't apply I just randomly redraw the ...
5
votes
0answers
29 views

Riddle: Assigning Students into Groups

Suppose you had a classroom with 25 students. You want to assign 6 homework assignments over the course of the term and for each of these assignments students will work in groups of 5. But you want to ...
0
votes
0answers
20 views

Other than the icosahedron in which each vertex has degree 5, is there any triangulation of the sphere that meets the following three conditions?

Every vertex has degree > 3. There is no separating triangle (a triangle with vertices of the graph both inside and outside the triangle). Every vertex-coloring using exactly four colors consists of ...
1
vote
3answers
41 views

Cayley graph is a tree iff group is free

I am looking at this proof of this claim that the cayley graph is a tree iff g is a free group with generating set S. For the direction '$\implies $' I see that they have assumed that there are two ...
0
votes
1answer
37 views

Number of paths in a graph with infinite nodes

Does a graph with infinite nodes that is not fully connected have a countably infinite or a uncountably infinite number of paths originating from a single node? We are only concerned with paths that ...
0
votes
0answers
7 views

DAG bipartite matchings vs. minimal path cover

Whenever $G=(V,E)$ is a DAG, we can look at the induced bipartite graph and find a maximum matching. Then the number of unmatched vertices in each part of the bipartition is supposedly exactly the ...
0
votes
0answers
31 views

Generalisation of edges in graph theory

Edges can be represented by tuples of sets of nodes. For example, the tuple $(\{A, B \}, \{C \})$ would represent the directed hyperedge from $A$ and $B$ to $C$. $1$-tuples represent undirected ...
5
votes
2answers
249 views

Is Category Theory similar to Graph Theory?

The following author noted: Roughly speaking, category theory is graph theory with additional structure to represent composition. My question is: Is Category Theory similar to Graph Theory?
0
votes
1answer
11 views

Equivalent definition of cograph

A cograph is simple graph defined by the criteria $K_1$ is a cograph, If X is a cograph, then so is its graph complement, and If X and Y are cographs, then so is their graph union X union Y and ...
0
votes
1answer
22 views

Are there triangulations of the sphere (see below) for which every vertex four-coloring consists of a single Kempe chain for each color-pair?

In other words, if 1, 2, 3, and 4 represent the four colors available and i and j are colors with i < j, then each proper coloring of the triangulation of the sphere using all four colors has one ...
0
votes
0answers
36 views

Graph decomposition

I want to decompose a (undirected) graph, into non-overlapping, complete subgraphs (i.e. every vertex belongs to exactly one subgraph), such that the number of subgraphs is minimal. Does anyone know ...
0
votes
1answer
13 views

Finding a vertex that can be a root after some operations.

We are given a Tree with N verticies and directed edges. We can change their directions, so all edges will lead to the root. But every edge belongs to one of K groups. If you change the direction of ...
1
vote
1answer
27 views

Graph Theory Matchings

Let $M$ be a matching in a graph $G$ with an $M$-unsaturated vertex $u$. Prove that if $G$ has no $M$-augmenting path starting at $u$ then $G$ has a maximum matching $L$ such that $u$ is ...
0
votes
1answer
18 views

Hamiltonian Graphs with Vertices and Edges

I have this question: Alice and Bob are discussing a graph that has $17$ vertices and $129$ edges. Bob argues that the graph is Hamiltonian, while Alice says that he’s wrong. Without knowing anything ...
0
votes
1answer
10 views

genus of a complete bipartite graph

How do I prove that the complete bipartite graph Km,n has genus ⌈(m−2)(n−2)/4⌉ please? I know that the genus of Kn is ⌈(n-3)(n−4)/12⌉ but I cannot obtain the required proof
1
vote
1answer
35 views

What is number of p-point subgraphs in n-point graph with average t connections?

I don't know graph theory, but I want to study this specific question for a while. I have no idea if this is a well known and studied question or not. I found it very difficult, and I don't know where ...
0
votes
1answer
15 views

Maximal weight of path in directed graph (using max-plus algebra)

I am working with matrices over the max-plus algebra $(\mathbb{R}_\max,\oplus,\otimes)$. For $A \in \mathbb{R}_\max^{n\times n}$, the graph $\mathcal{G}(A)$ has vertex set $\{1,\dots,n\}$ and edges ...
2
votes
0answers
16 views

Optimality of lower bounds for Max-cut on specific graphs

The Max-Cut problem asks to find a subset $S$ of the vertices of a graph (with $m$ edges) such that the number of edges from $S$ to it's complement is as large as possible. The size $|M|$ of a max cut ...
1
vote
1answer
12 views

A cut is minimal iff forward arcs saturated and reverse arcs flowless

Let $G = (V,A)$ be a network with arc capacity function $c$ and let $f$ be a flow on $G$. An arc $(x,y) \in A$ is said to be saturated if $f(x,y) = c(x,y)$ and flowless if $f(x,y) = 0$. In Flows in ...
0
votes
1answer
41 views

What is known about optimization of spectral properties of matrices over finite fields?

[I am solving the characteristic polynomial over complex numbers but since the matrices are symmetric all eigenvalues are real] Like for symmetric $d-$regular matrices over 0/1 or 0/1/-1 what are ...
0
votes
2answers
20 views

Complement of a Regular Graph

Prove whether or not the complement of every regular graph is regular. What I have: It appears to be so from some of the pictures I have drawn, but I am not really sure how to prove that this is the ...
0
votes
1answer
26 views

Given graph $G=(V,E)$, explain what it means if $uv\notin E$, but containing cycle with edge $uv$

An exercise question asks me to find the vertices $uv$ given graph graph $G = (V,E)$ such that $uv\notin E$, and $G + uv$ contains a cycle with edge $uv$. I am having some trouble understanding ...
0
votes
1answer
31 views

Applications Of Strongly Regular Graphs

I am currently working on a thesis regarding some existence problems on strongly regular graphs. But it is actually my first encounter with them. Though i am done solving my problems, But in order to ...
4
votes
1answer
47 views

Problems with a proof involving graphs and groups

I'm studying an article that is the main literature when it comes to non-commuting graph : this article. Originally, a non-commuting graph of a group (denoted by $\Gamma_G$) is a graph whose vertices ...
0
votes
0answers
19 views

Cubic 3-edge connected graph which is neither hamiltonian nor hypohamiltonian

Is there such a thing as a cubic 3-edge connected graph which is neither hamiltonian nor hypohamiltonian? Intuition says yes, but I'd like a confirmation (and an example, if possible). Thank you!
1
vote
0answers
59 views

Are modular Collatz graphs strongly connected?

A while ago, I stumbled on the idea of representing the Collatz function, modulo a prime $p$, as a directed graph. Define, as usual $$ T(x) = \begin{cases} (3x+1)/2 & \text{if $x$ is odd,} \\ x/2 ...
2
votes
1answer
37 views

“Every planar graph has a vertex of degree at most 5” So what's wrong in this case?

As far as I know, a planar graph is simply defined as a graph that can be drawn in the plane with none of its edges crossing. This I understand. However, I came across a problem that says: "Every ...
0
votes
0answers
25 views

Real World Example for the Generalized Vehicle Routing Problem.

I’m writing my master thesis in applied mathematics and I need some help finding a real world application to the problem that I’m studying. My thesis deals with the Generalized Vehicle Routing ...
-2
votes
0answers
32 views

Mathematical proof of the emergence of graph pattern [on hold]

If anyone can define a emergence of graph pattern with mathematical notation, please post a response. For example trinagles in social graph. Graph (all nodes, all relationships): A graph is a pair G ...
0
votes
0answers
15 views

Does loops affect a graph when I'm creating a trail or path?

I have read that in order for there to be a trail, no edges must be repeated in the walk and for a path there must be no repeated vertices. However, it doesn't say anything about whether or not loops ...
1
vote
1answer
24 views

Question on definition of group acting on a topological space.

I know that a group can act on a graph by acting on the set of vertices on a graph. I also know that a graph can be viewed as a CW complex and therefore a topological space and i am trying to bridge ...
-2
votes
0answers
43 views

Strongly connected components problem help with using lexicographic order to create a graph

The edges of directed graph $G$ on node set $\{0, 1\} ^ 3$ are as follows: There is an edge from $a_1a_2a_3$ to $b_1b_2b_3$ if and only if $b_3 \in \{a_1,a_2\}$; $b_1 \in \{a_2,a_3\}$; $b_2 = ...
-5
votes
0answers
29 views

Approximation algorithm for mine packing problem [on hold]

Problem: In the Mine Packing Problem, we are given an undirected graph G = (V, E), and wish to find a set of vertex-disjoint trees of depths 1 (all leaves connected directly to the root). The goal is ...
0
votes
0answers
22 views

Euler walk by joinning subgraphs

I am studying the book: Graph Theory, Trudeau (Dover). Excersise 11, chapter 8, goes as follows: Prove: if $n\ge2$ and G is connected with $2n$ odd vertices then $G$ has n open walks which, together, ...
1
vote
1answer
20 views

How many complete triangulations of the sphere are there in which every vertex has exactly degree five?

I know of one with 12 vertices, 20 faces, and 30 edges. Are there any others? Almost sorry I asked the question. The answer is trivial. Use Euler's formula and the unique solution pops out.
0
votes
0answers
17 views

Can someone advice edge contraction tool?

I need to show how edge contraction happening in graphs and the best way for it is visual presentation. Maybe someone can give an advice about a tool where it can be simply represented. Maybe a ...
-2
votes
0answers
31 views

Does new matrix also have integral eigen values?

$K_n$ is complete graph on n vertices. Laplacian matrix of $K_n$ has integer eigenvalues. If we are taking compliment of a $K_m$ (alongwith n-m isolated vertices) ; $m<n$ in $K_n$, Does Laplacian ...
3
votes
2answers
69 views

Non-factorizable graphs in which every edge can be extended to a maximum matching

All graphs in this question are finite, simple, undirected, and unweighted. A graph is said to be factorizable if has a perfect matching, and non-factorizable otherwise. An edge in a graph is said to ...
1
vote
2answers
25 views

Prove every strongly connected tournament has a cycle of length k for k = 3, 4, … n where n is the number of vertices.

Prove every strongly connected tournament has a cycle of length $k$ for $k = 3, 4, … n$ where $n$ is the number of vertices. I know that I need to prove this thm by induction but I am not sure how.
0
votes
0answers
13 views

Decomposing an undirected graph into trails

Any undirected graph, $\mathcal{G} = (\mathcal{V}, \mathcal{E})$, has an even number of odd-degree vertices. If $\mathcal{G}$ has $2k$ odd-degree vertices, where $k > 1$, then $\mathcal{G}$ can be ...
0
votes
1answer
25 views

prove there is no tournament with 4 vertices and 4 kings

Can anyone help me prove there is no tournament with 4 vertices and 4 kings. (Also written as no (4,4) flock) I have been trying to strategize a starting point for the proof but I cant come up with ...
1
vote
0answers
17 views

Reduction from Hamilton Path to Hamilton Cycle [closed]

How to reduce the Hamilton Path problem to the Hamilton Cycle problem? I found only the reduction of Hamilton Cycle to Hamilton path.
1
vote
0answers
10 views

Random DFS properties

Have there been any work analyzing some properties of random DFS walks? By that I mean a DFS search, which chooses the next node to visit with uniform probability. i.e, it still refrains from visiting ...
0
votes
0answers
16 views

Graph Theory: small-worldness

I have two groups, each including several networks. I calculate following three network measures for each network clustering coefficient characteristic path length small-worldness (by comparing 1 ...
1
vote
0answers
33 views

Linear Algebra and Graph theory

I haven't done any linear algebra for a long time and currently reading about linear algebra in graph theory and had a few queries. So i'm looking at the definition of a vertex space. Firstly let ...
3
votes
1answer
37 views

Conjectured diagonal Ramsey numbers

While doing some reading on the Wikipedia page for Ramsey numbers, I stumbled upon OEIS sequence A120414, which lists the allegedly conjectured values of the diagonal Ramsey numbers $R(n,n)$. I ...
0
votes
0answers
25 views

Proof that graph is 2-connected

Let $G=(V,E)$ be graph where $|V| \geq 3$. For any three vertices $x, y, z$ there is path from $x$ to $y$ in G that it doesn't contain vertex $z$. How can I proof that G is 2-connected in terms of ...
-1
votes
1answer
38 views

Determine if it's a tree and find K [closed]

A graph with K vertices of degree 4, and 2K + 2 vertices of degree 1. Is it a tree? Find K
0
votes
0answers
33 views

Graph Coloring and Complete Graph

If a graph is k-colorable, then does it imply that it must have a k-complete graph as it's subgraph? For example if a graph has chromatic no = 5, then is this sufficient to imply that it must have K5 ...