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

4
votes
1answer
37 views

Two pawns walking in a complete graph

We have a complete graph $G = \langle V,E\rangle$ with non-negative values on edges. Let $C = \{v_1,v_2,\ldots,v_n\}$ be an ordered collection of $G$'s vertices. At the beginning we have two pawns in ...
0
votes
1answer
17 views

Counting spanning trees in labelled graphs

I have some troubles with counting spanning trees, it seems completely abstract to me. First one is cycle with n vertices - it's just n, because we can move each number n times like so: ...
-1
votes
1answer
81 views

Proving by induction on the number of vertices that: every acyclic simple graph is bipartite

Prove that every acyclic simple graph is bipartite, by the use of induction. I have quite some trouble with induction. Specifically, I know that acyclic graphs have at least one vertex that has a ...
2
votes
2answers
31 views

Give a formal argument why there is no planar graph with ten edges and seven regions. Here is my answer

I'm really new to a graph theory, and I have to answer the following question: give a formal argument why there is no planar graph with ten edges and seven regions. Here is my answer: Using ...
0
votes
0answers
35 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
29 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
1answer
40 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 ...
1
vote
0answers
14 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
40 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
33 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
22 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
33 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
16 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
41 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
18 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
12 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
38 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
1answer
31 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
21 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
18 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
54 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 ...
0
votes
0answers
38 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
55 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
44 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
14 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
257 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
26 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
29 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 ...