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
12 views

Find if it is possible to draw a closed (cycle; not a path) continuous line…

... that crosses exactly once (only once) each interior line segment of the rectangle, whilst staying inside the rectangle for these 2 rectangles. My immediate reasoning was to remove all the outside ...
0
votes
2answers
27 views

The maximum no. of edges in a DISCONNECTED simple graph…

... on n vertices when it is not connected being equal to (1/2)(n - 1)(n - 2)... I can see that for n = 1 & n = 2 that the graphs have no edges... however I don't understand how to derive this ...
1
vote
3answers
22 views

Notation for two-vertex graph with m edges

Is there standard notation for the graph on two vertices with $m$ edges between them?
1
vote
1answer
12 views

Kirchoff Matrix -Tree Theorem

I'm reading a proof of the Kirchoff Matrix -Tree Theorem: If $G$ is a simple connected graph, $D$ the diagonal matrix with the vertices' degrees and $A$ the adjacency matrix, then in $M = -A+D$ ...
0
votes
0answers
27 views

Kempe chain color swaps in a partially colored map

Question: In this partially Tait's colored map, using only Kempe chain color swaps (as many as wanted), how many differently colored maps can I have? This map has these Kempe chains: (R,G) - 1 - ...
0
votes
1answer
21 views

Are minimum cut communities maximal?

I am looking at the paper Graph Clustering and Minimum Cut Trees by Flake et al. Let $G(V, E)$ be some undirected weighted graph. Definition. Let $s, t\in V$ be given. Let $(S, T)$ be the minimum ...
0
votes
0answers
16 views

Complexity class of determining the gracefulness of an arbitrary graph G

Deciding if the a graph is a graceful one, is an NP problem. But my question ‎is "is there any proof that shows it is NP-Complete?" ‎ I've searched for the answer in many resources and papers, among ...
4
votes
2answers
39 views

existence of K_3 in a graph with n^2+1 edges

I was working on this problem for quite a long time and was unable to solve it. Any help will be appreciated. Let $G$ be a graph with $2n$ vertices ($n \in \mathbb{N})$ and $n^2+1$ edges. Show that ...
2
votes
2answers
56 views

Some kind of latin squares

Consider we have an $n\times n$ square. And for each element $a_{ij}$ there is a $L_{ij}$ set of permissible values(numbers) where $|L_{ij}| = n - 1$. Need to choose a value for each $a_{ij}$ element ...
0
votes
1answer
25 views

How to understand the perfect binary tree formula?

I got this paragraph by reading "python algorithm", in which it mentioned `some knights participate in an knockout match, how many mathes do they need to produce the winner. It's answer says: I'm ...
0
votes
1answer
24 views

How to check if a 2D mesh is connected

I'm trying to optimize structures by using FEM and genetic algorithms (GA), the FEM solver is a commercial one, and I'm programming the GA. Something like this. My first approach is simple, just ...
1
vote
1answer
41 views

What's the 1-dimensional topology of a graph?

I'm reading through this paper here downloads.hindawi.com/journals/mpe/2013/815035.pdf where they say "Since a graph can be equipped with a topology to turn it into a a one-dimensional space, we can ...
0
votes
1answer
23 views

Labelled graph minor theorem

Note: this isn't duplicate to this: Does the Robertson-Seymour theorem apply to vertex-labeled graphs? One of equivalent definitions of graph minorship is the following: $G_1$ is minor of $G_2$ if we ...
1
vote
1answer
14 views

Chromatic polynomial of a graph $G$

Let $G$ be the graph in picture: calculate the chromatic polynomial of it. My attempt: I assume that $G(K_n,x)$ is the number of distinct colors of the complete graph with $n\geq1$ vertices with ...
0
votes
1answer
44 views

Algorithm for finding contradictions in a directed graph that represents implications

I need an algorithm that does this: For a directed graph where nodes represent boolean values and edges represent implication (implies TRUE and implies FALSE): If (arc exists between any ...
3
votes
0answers
29 views

A probability of a monochromatic cycle on a randomly colored lattice graph.

Let $G$ be an undirected $6 \times 6$ lattice graph. The $36$ vertices of $G$ are each randomly colored with one of $5$ colors with equal probability. Such a coloring is called "successful" if and ...
0
votes
0answers
28 views

Determine the smallest integer n>1 such that there exists a connected graph G of order n such that |Aut(G)|=1? [on hold]

Determine the smallest integer n>1 such that there exists a connected graph G of order n such that |Aut(G)|=1?
-2
votes
0answers
17 views

Investigating the graph whose vertices are the subsets of an $n$-set and edges occur whenever two subsets intersect in exactly two elements. [on hold]

The $2^n$ vertices of a graph $G$ correspond to all subsets of a set of size $n$, for $n \geq 6$. Two vertices of $G$ are adjacent if and only if the corresponding sets intersect in exactly two ...
0
votes
0answers
42 views

Finding the smallest max eigenvalues for related matrices?

While messing around with a spectral approach to a graph coloring question, I happened upon a type of problem I hadn't seen before. Suppose you have two symmetric $n$ x $n$ matrices in the form ...
1
vote
1answer
21 views

Suppose that a planar graph has $k$ connected components, $e$ edges, and $v$ vertices. Also suppose that$\dots$

Question: Suppose that a planar graph has $k$ connected components, $e$ edges, and $v$ vertices. Also suppose that the plane is divided into $r$ regions by a planar representation of the graph. Find a ...
0
votes
2answers
30 views

Prove that $G$ is Hamiltonian.

Let $G=(V,E)$ be a connected graph which is not a tree. Prove that if for every cycle $C$ of the graph G and for any $v \in V(G)- V(C)$ there are more than $\frac{|C|}{2}$ edges from $v$ to $V(C)$ ...
3
votes
0answers
32 views

What are the algebraic and topological properties of a tree (graph theory), and what are any possible connections?

I'm a non-mathematician working with trees (mostly rooted and oriented trees). Typically, I understand them as join-semilattices, so they have an implicit algebraic structure: they form a subgroup ...
0
votes
2answers
51 views

Determinant of identity minus adjacency matrix

Let $M$ be the adjacency matrix of a directed graph $G$. Is there any known relation between $\det(\textrm{id}-M)$ and the cycles of $G$? It is easy to see that if $G$ is acyclic then this ...
3
votes
1answer
68 views

What are the big issues in modern graph theory?

This is inspired by the similar question on modern set theory. I've read through the open problems in graph theory on Wikipedia's list of unsolved problems in mathematics, but what I'm looking for is ...
1
vote
1answer
33 views

proof of Konig's Theorem for bipartite graphs from Menger's Theorem

Could someone provide me with a good reference for a proof of Konig's Theorem for bipartite graphs from Menger's Theorem? Konig's Theorem is as follows: For a bipartite graph $G$, the maximum size ...
0
votes
0answers
29 views

Number of walks in a Graph from u to v, containing exactly k edges

I have read here that if the adjacency matrix is represented by $A$, then the entry $A[i][j]$ in the matrix $A^{k}$ gives the number of walks from $i$ to $j$ containing $k$ edges. What is the proof ...
-3
votes
0answers
33 views

graph problem homework helps [closed]

1) Prove that if all edge-costs are different, then there is only one cheapest tree. (Hint: Do a proof by contradiction, following the proof of Kruskal’s theorem. Make sure to keep track of the costs ...
-1
votes
1answer
45 views

The union of two connected graphs is connected [closed]

Let $G = (V,E)$ be a graph and let $H_1 = (V_1,E_1)$ and $H_2 = (V_2,E_2)$ be two connected subgraphs of $G$ that have at least one node in common. Prove that the graph $H = H_1\cup H_2 = (V_1\cup ...
3
votes
2answers
39 views

Prove that there is no bipartite graph on $14$ vertices with this degree sequence.

Prove that there is no bipartite graph on $14$ vertices with degree sequence: $$6, 6, 6, 6, 6, 6, 6, 6, 5, 3, 3, 3, 3, 3.$$ I assume a vertex with degree $5$ breaks this graph from being ...
0
votes
0answers
17 views

Fint $N$ games played by minimal number of players

I got a following problem: There is a database which looks like this: $$\operatorname{GameId}||\operatorname{PlayerId}$$ $$1||1$$ $$1||2$$ $$\dots||\dots$$ where every game was played by 10 ...
2
votes
1answer
19 views

Non probabilistic algorithm for min-cut problem?

I know about Karger's algorithm and its variations, all of them being probabilistic. Is there non-trivial (i.e. non-brutefoce) deterministic algorithm for mincut problem?
1
vote
0answers
17 views

Gallai & Milgram path covers theorem from Diestel

I have a question about the theorem of Gallai and Milgram stating that every directed graph has a path cover $P$ such that one can make an independent set of $G$ by picking vertices from each of the ...
0
votes
0answers
20 views

Tree-width of a graph

What is the tree width of the graph? Here are the relevant definitions from my textbook: We define the width of an induced graph to be the number of nodes in the largest clique in the graph ...
-1
votes
0answers
9 views

network design: why can't an almost satisfied proper function violated by all given sets?

I'm reading a book about (survivable) network design and i have a problem understanding a lemma. Given an undirected graph G and $V(G)$ its nodes and $E(G)$ its edges. The book defines a proper ...
2
votes
0answers
17 views

What does scale free mean in terms of a scale free graph

My understanding of a scale free graph is as follows: Say if we have a large graph $G$ if we were to take random partitions of $G$: $g1, g2,\dots$ Any centrality metric (such as page rank, degree ...
0
votes
0answers
26 views

Maximum length of any path from any root in a DAG

Let $\max \emptyset := -1$. For any directed acyclic graph $G = (V,E)$, let $f: V \to \mathbb{N}_0$ such that $\forall v \in V: f(v) = 1 + \max \{f(u): uv \in E \}$. Which terms are used for this ...
0
votes
1answer
71 views

Graph question concerning components.

Question Suppose that an undirected graph of order $n$ and size $m$ contains two vertices $s$ and $t$ of distance more than $n/2$. Show their exists a vertex $v$, not equal to $s$ or $t$, such ...
0
votes
0answers
24 views

Algebra on trees?

Given a forest of trees, I am interested in tree recombination operations that produce me a sub-forest spanned by some selected trees. To me, it somehow resembles space and spanned subspace in ...
6
votes
1answer
65 views

Where can I download the approx 1500 Appel-Haken reducible configurations in the Four-Color-Theorem proof?

Where can I download computer representations of the approximately 1500 Appel-Haken reducible configurations in the Four-Color-Theorem proof? The Wikipedia article ...
0
votes
3answers
36 views

How to write a summation function that counts the number of nodes in a tree?

I come from a programming background and am interested in learning how to represent some things as simple equations, as an entry into thinking mathematically. How do you represent a tree structure as ...
0
votes
1answer
17 views

FKT algorithm and adjacency matrices

The Wikipedia article on the FKT algorithm says that one finds the number of perfect matchings in an undirected planar graph $G$ as follows. Find a graph $H$ that is a directed version of $G$, such ...
0
votes
2answers
159 views

Help showing that every walk of length $k$ from $x$ to $y$ in a graph is a path.

If I were to suppose $x$ and $y$ are two vertices in the same connected component of a graph, and let $k$ be the distance between them, how would I prove that every walk of length $k$ from $x$ to $y$ ...
0
votes
0answers
24 views

Tightest upper bound for $\sum_j g_{ij}$ of an adjacency matrix of a graph

If I have an adjacency matrix of a graph $G$ (i.e. $g_{ij}=1$ if $i$ and $j$ are connected and $g_{ij}=0$ if not. $g_{ii}=0$), is there any tighter upper bound on $\sum_{j} g_{ij}$ than just $n-1$ ...
0
votes
1answer
35 views

Showing exitence of a path in Graph Theory

If $P$ and $Q$ are paths in a connected graph that have no vertices in common, then there exist vertices $u$ and $v$ and a path $P′$ such that $u$ is on $P$, $v$ is on $Q$, $P′$ is a $u–v$ path, ...
0
votes
1answer
68 views

Graph theory / vertex-set list representation

If I were to consider a graph with vertex-set V= {1, 2, 3, ... 10} with the edges taken as all the pairs {x, y} of distinct members of V that have a prime factor in common, how would one write the ...
0
votes
1answer
36 views

Width and height of binary tree is $\theta(n)$?

we know this definition: Given a binary tree, Width of a tree is maximum of widths of all levels. Let us consider the below example tree. ...
0
votes
0answers
36 views

Graph Theory Proof - Hamilton Decomposition of 4-regular Graphs

I've been asked to prove the following; Let $G$ be a 4-regular graph, let $v$ be a vertex of $G$, and let $u_1, u_2, u_3, u_4$ be neighbours of $v$ in $G$. Replacing $v$ with a $K_4$ means adding ...
1
vote
0answers
16 views

How many graphs on n nodes, with each component a coherently directed tree

For a positive integer $n$ choose $m$ with $1 \le m \le n$ and let $X$ be a set with $|X|=n$. choose $x_j \in X$ for $j=1,...,m$. Define $m$ directed graphs $X_j$ in the following way: Initially we ...
0
votes
0answers
11 views

Min cost flow problem for hypergraphs and multidimensional assignment problem

Multidimensional assignment problem is NP in general. There is an algorithm, which transforms the common assignment problem into min-cost flow problem. Why we can't do the same operation onto ...
0
votes
0answers
29 views

Proof Checking - Hamiltonian Decomposition/Graph Theory

I've been asked to prove the following statement; If a graph has a Hamilton decomposition, then it is regular of even degree I just wanted to check whether the proof I've outlined for it is on ...