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
0answers
18 views

Convex polyhedra with edges of equal length

This is again a natural category of polyhedra without having an own name. Is it possible, that their graphs are the same as the graphs of polyhedra with faces of regular polygons? My question is ...
0
votes
0answers
23 views

Calculate distance between known intersecting points

I have been working on this problem for awhile now and I think I just need a few fresh minds to help me out. I have 4 lines that intersect and form a shape. This is part of a much larger problem, ...
1
vote
0answers
22 views

Interesting Graph Theory “WOMVIES” problem

Here is an interesting problem: A graph is a set of vertices (points), some pairs of which are joined by an edge. For this problem, we will not allow an edge to join a vertex to itself (i.e., no ...
0
votes
0answers
10 views

Expected number of leaf nodes in some theoretical graph models

If a leaf node of a graph refers to a node having the degree of 1, how can one compute the expected number of leaf nodes of: (A) a random graph (e.g., Erdos-Renyi graph), (B) a small-world graph ...
2
votes
1answer
28 views

Percolation over the integers

Imagine a simple undirected graph with a countably infinite number of vertices, each labeled with an unique integer $v \in \mathbb{Z}$. Connect the vertices by edges randomly such that Each vertex ...
0
votes
1answer
28 views

Tutte matrix - Determinant

I'm trying to understand the proof of the "magic theorem" about the Tutte matrix which states: Let $T$ be the Tutte matrix of $G(V, E)$. Then, $$\det(T) = 0 \quad\Longleftrightarrow\quad G ...
1
vote
0answers
21 views

question regarding edge space

Given a graph $G=(V,E)$ and it's edges space $\mathcal{E}(G)$ in the book by Diestel it defines given two edges sets $F,F'$ and their coefficients $\lambda_{1},...,\lambda_{m}$ and ...
0
votes
1answer
28 views

The number of edges in a tree is $n-1$

I am trying to prove that the number of edges in a tree is $n-1$ where $n$ is the number of vertices. I do not wish to use induction. I already have established that a tree is a planar graph. Now my ...
0
votes
1answer
15 views

Breaking connectedness by removing edges from the complete graph $K_n$

Given the complete graph on $n$ vertices $K_n$, what is the smallest number of edges you can remove in order to separate the graph into two disjoint subgraphs? I consider vertices without edges to be ...
0
votes
0answers
39 views

Does the graph exist with these degrees?

$(11,2,2,2,2,2,2,2,1)$ Is it possible that a degree of a vertex can be 11 ? However, there are only 9 vertices. Does the graph exist?
2
votes
0answers
16 views

Max cut problem

I've just looked at the standard proof using the probabilistic method stating that the max cut problem has a lower bound of $|E|/2$ for any graph $G=(V,E)$. More specifically if $X$ is the random ...
0
votes
1answer
10 views

What are existing methods to count colored subgraph frequencies in a large colored directed graph?

I have a directed colored large network or graph. By 'color' I mean that nodes are of different categories. There are some small 3 or 4 node colored directed subgraphs. I need to know how to count ...
0
votes
0answers
23 views

Vector multiplication with both subscript and superscript, in training algorithm for McCollugh-Pitts neurons?

Can someone here help me understand what's going on with the Vis, with both the subscript and superscript notation (as included in the images supplied below)? Is it Einstein Notation? I'm almost ...
0
votes
1answer
34 views

size of enclosed area in travelling salesman problem optimum

Can we say the size of enclosed area of optimum solution is greater than enclosed area of any other solution in a TSP problem?
0
votes
1answer
30 views

What is the walk of this graph?

A walk that is not a trail from vertex 1 to vertex 3; A trail that is not a path from vertex 1 to vertex 3; A path from vertex 1 to vertex 3. How can I describe these walks?
1
vote
0answers
20 views

Icosahedral Graph

Let $Γ$ be a graph cospectral with the icosahedral graph having spectrum $\{[5]^1,[\sqrt{5}]^3, [-1]^5,[-\sqrt{5}]^3\}$. I have shown that Γ has 12 vertices, 30 edges, regular with each vertex having ...
1
vote
1answer
20 views

The dual of transporting problem

So basically I'm trying to figure out what does a certain variable in dual of transporting problem mean. Transporting problem in matrix form: (We are searching for a min cost of transferring goods ...
1
vote
0answers
17 views

Co ordinate independent linear algebra over graphs

It is frequently said that Linear algebra is not correct until it is coordinate free or something to that effect and indeed, almost all the major results can be stated without picking a basis. ...
0
votes
1answer
12 views

Solving Through The Use Of Handshakes.

Let $G$ be a graph. Use the Handshake Theorem to prove that $\delta(G)\nu(G) \le 2\varepsilon(G) \le \Delta(G)\nu(G)$. So the first step to solve this I know is that you need to know what ...
0
votes
1answer
21 views

Condition to detect cycle in graph

Which of the following condition is sufficient to detect cycle in a directed graph? A. There is an edge from currently being visited node to an already visited node. B. There is an edge from ...
0
votes
0answers
8 views

Calculating the Estrada Centrality

The Estrada centrality of a node i is given by $E_i =(e^A)_{ii}$ where $A$ is an adjacency matrix Express the Estrada centrality in terms of the number of loops of length r $N^r_{ii}=[A^n]_{ii}$ ...
0
votes
1answer
53 views

What kind of tree it is? How to solve the problem?

I have a tree with following configuration: n is the number of different vertices v ($0 \lt v \le n$). Each vertice ...
1
vote
0answers
35 views

about complement of a graph

Let $G$ be a $k-$regular graph on $n$ vertices. we know that if $k\geq n/2$, then $G$ is a connected graph. Now, if we take complement of graph $G$ and denote it as $\bar G$ then $\bar G$ will be ...
2
votes
1answer
22 views

Family of sets without 2 disjunct elements, prove the statement

Suppose, that the $F \subseteq 2^{[n]}$ family of sets doesn't have two disjunct elements. Prove, that there is always an $F' \subseteq 2^{[n]}$ family of sets, which contains $F$, $F'$ has no ...
0
votes
1answer
10 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
28 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 ...
7
votes
0answers
53 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
43 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
42 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
11 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
35 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
254 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?
1
vote
1answer
21 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
27 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
38 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
15 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
28 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
19 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
2
votes
1answer
52 views

Counting 5-point, 4-edge subgraphs of a chess board

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
25 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
17 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
13 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
42 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
21 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
29 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
32 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
50 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!