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

3
votes
1answer
62 views

Another Evaluation of the Ramsey number $\mathcal{R}(3,3,3)$

The problem Show that $\mathcal{R}(3,3,3)=17$ The story behind the problem and some notation It was first proven by Greenwood and Gleason in 1955 in their paper Combinatorial relations and ...
2
votes
1answer
60 views

Graph Theory text for social scientist.

I am a graduate student in Economics. I have a decent grounding in maths, but I've never studied graph theory or combinatorics. I need to study graph theory in order to analyse production networks. ...
4
votes
1answer
219 views

Prove the connected components are uncountably many

Let $G$ a graph with vertices all the points in $\mathbb{R}^2$. An edge exists if and only if the distance between two points is a rational number. Prove that the connected components are ...
0
votes
0answers
10 views

Extract and search an unweighted multigraph from an undirected weighted graph?

I have an undirected weighted graph G(V,E) where the nodes are bus stops and the edges are the distances between the stops. I've implemented a basic Dijkstra to search the shortest path (s, t) which ...
-2
votes
0answers
21 views

Prove that for any polyhedron [closed]

Prove that for any polyhedron there are two faces with the same number of vertices.
-1
votes
1answer
37 views

the sum of numbers at any row and at any column of this matrix is exactly 1.

All entries of an n × n matrix are non-negative. It is known that the sum of numbers at any row and at any column of this matrix is exactly 1. Prove that you can choose n positive entries such that ...
0
votes
1answer
15 views

Name of a graph that shows various strengths

I am looking for the name of a graph used to show various strengths. It is a polygon and may look like this: _ | | | | | * | _ Where the ...
1
vote
1answer
27 views

Lower bound for the size of a maximal matching in a general graph

Let $G=(V,E)$ be a graph, let $M\subseteq E(G)$ be a maximal matching, and let $M^\star\subseteq E(G)$ be a maximum matching. Prove that $|M|\ge |M^\star|/2$. Any hints on how to prove this?
1
vote
2answers
29 views

Path and cycle length proof

How can we prove this proposition : Every graph G contains a path of length $ \delta(G)$ and a cycle of length at least $ \delta(G) + 1$, provided that $\delta(G) \geq 2 $. ($ \delta(G)$ is the ...
7
votes
0answers
53 views

Dominating a Four Dimensional Chessboard with Rooks

There is a family of chess problems where you try to dominate a board with as few copies of a given piece as possible. The chessboard is dominated if every square either contains a piece, or is ...
2
votes
1answer
26 views

Graph Theory-Eulerian Path?

In a certain country, $40$ roads lead out of each city. When all roads are open, it is possible to travel from any city to any other. Each road leads from one city to another; there are no dead end ...
1
vote
1answer
35 views

help with graph theory question

Let $A_1A_2A_3A_4$ be a square, and let $A_5,A_6,A_7,\ldots,A_{34}$ be distinct points inside the square. Non-intersecting segments $\overline{A_iA_j}$ are drawn for various pairs $(i,j)$ with $1\le ...
0
votes
1answer
37 views

sitting around a table- graph theory?

$50$ mathematicians attend a conference at which each knows $25$ other attendees. Show that you can select $4$ of them who can then be seated at a round table, such that each person at the table knows ...
2
votes
0answers
14 views

Graph Entropy - A Tractable Measure to Measure Distinguishability of Neighbourhoods

Given a labelled directed graph G, I am interested in a measurement of G that captures how distinguishable arbitrary connected sub graphs of G are. Labels may repeat and as such two or more different ...
0
votes
1answer
27 views

Chromatic number of a hypercube

What is the chromatic number $\chi(Q_4)$ of a four-dimensional cube. I know that all Hypercubes $Q_d$ are bipartite, so then this would yield $\chi(Q_4) = 2$, because every bipartite graph has ...
0
votes
0answers
13 views

Network Coding multicast r symbols simultaneously. Physically How?

I understand how network coding works but physically how r symbols can be multicast to all destinations from one source? For example in following butterfly network, there are two symbols which can be ...
1
vote
1answer
53 views

Count the paths in a graph

For a given graph $G(V,E)$ $V = \{ (x,y) | x = \{0,1, ... , m\}, y = \{0,1, ... , n\} \}$ $E = \{ \{(x,y), (u,v)\} | (x=u \text{ and } |y-v|) = 1 \text{ or } (|x-u| = 1 \text{ and } y=v) \}$ How to ...
0
votes
1answer
21 views

Proof If a tree is not trivial, then there are at least two pendant vertices?

I have the following Proof but could not understand it Proof. If a tree has $n(≥ 2)$ vertices, then the sum of the degrees is $2(n − 1)$. If every vertex has a $degree ≥ 2$, then the sum will be $≥ ...
9
votes
0answers
48 views

What can we say about the graph when many eigenvalues of the Laplacian are equal to 1?

The Laplacian of the graph has all the eigenvalues real and non-negative, the smallest being 0. I have a graph where the second smallest eigenvalue (the so called algebraic connectivity) is equal to ...
-1
votes
1answer
26 views

Perfect matching and maximum matching

In a graph where a perfect matching is possible, is that perfect matching also always the maximum matching?
3
votes
0answers
47 views

What is the diameter of the Cayley graph of $S_n$ w.r.t the generator $\{(12),(23),…,(n−1n)\}$?

Given a symmetric group $S_n $ and the generator set : $S = \{(12),(23), . . . ,(n − 1 n) \}$ is there any closed form expression for the diameter of the Cayley graph generated by this set of ...
1
vote
1answer
20 views

Exlamation about a claim of an existing such cycle in a simple Graph

Suppose the following situation: this is found at (Let G be a graph of minimum degree k > 1. Show that G has a cycle of length at least k+1) Let $P=v_0v_1 \dots v_l$ be a longest path in $G$. ...
2
votes
1answer
62 views

graph theory matrix

all entries of an $n \times n$ matrix are non-negative. It is known that the sum of numbers at any row and at any column of this matrix is exactly 1. Prove that you can choose n positive entries such ...
0
votes
0answers
29 views

Looking to get a handle on SSCG(3) (which is much, much larger than TREE(3))

TREE numbers grow rapidly: TREE(1) = 1, TREE(2) = 3, and a lower bound for TREE(3) is A(A(...A(1)...)), where the number of As is A(187196) and A(n) is a version of Ackerman's function. That's ...
1
vote
0answers
40 views

Deriving deletion-contraction formula from Subgraph Expansion of Chromatic Polynomial

Given a graph $G=(V,E)$, the chromatic polynomial $P(G,q)$ counts the number of $q$-colorings of a graph $G$. It satisfies the deletion-contraction formula: \begin{equation*} P(G,q) = P(G-e, q) - ...
1
vote
1answer
21 views

Complexity of finding M nodes in a graph to maximize the pairwise minimum distance between nodes

I want to know the complexity of finding a set of M nodes, $\{U_1,\dots,U_M\}$, in a given graph $G$, to maximize $d(U_i,U_j)$ over all pairs $i\neq j$, where $d(\cdot,\cdot)$ is the length of the ...
1
vote
1answer
23 views

combinations of graphs with 2 vertices

I am reading graph theroy. Here author mentions that the number of possible digraphs is truly huge. Each of the $V^2$ possible directed edges (including self-loops) could be present or not, so the ...
0
votes
1answer
31 views

Relation between edge expansion of graph and sparsity

I was going through the lectures of Graph Partitioning and Expanders - Stanford Online. In lecture 1, near the end of page 5, I came across this inequality for regular graphs: $$\phi(S) \leq h(S) \leq ...
2
votes
0answers
17 views

Using Erdős–Szekeres theorem for graph with 50 vertices

Let $G$ be a graph with $50$ vertices such that for every $4$ vertices there are $2$ that have no edge between them (independent). I want to prove that $G$ has a group of $5$ independent vertices.My ...
1
vote
1answer
28 views

proof that a cycle space is a subspace

I'm looking at the following proof that the cycle space of a graph is indeed a subspace, which I don't believe to be correct. proof: It suffices to prove that $\mathcal{C}$ is closed under $+$ ...
0
votes
1answer
38 views

maximal planar bipartite graphs

I know that a maximal planar graph is a graph in which no more segments can be added to connect more vertices because then it won't be planar, but I trying to define what a maximal planar bipartite ...
0
votes
0answers
11 views

List of graph data points, need accurate calculation/estimate formula for excel

So I'm working on a small project that will use a calculation in excel, I'm nearly there and the only piece missing is being able to accurately estimate a data point from the following set of data ...
-3
votes
1answer
38 views

Turan graph maximizes the minimal vertex degree

Prove that for every graph $G$ with $n$ vertices and $tr(n)$ edges, the following inequality holds: $$\delta(G) \le \delta(T_r(n))$$ where $T_r(n)$ stands for Turan's graph and $tr(n)$ for its ...
1
vote
1answer
59 views

If $G$ is simple and $deg^+(v)\geq k \geq 1 \space \forall \space v \in V$ there is a simple cycle of at least size $k+1$

I have the following proof but it is tough could someone help me to understand it, Proof: Start at an arbitrary node $v$ and mark it, and so on until you have marked all nodes in the series then a ...
0
votes
2answers
50 views

Proof that if all vertices have degree at least two then G contains a cycle

Here is the proof, but please correct me if wrong : We assume $G$ is simple and let $P$ be the longest path $=v_0v_1v_2\ldots v_{a-1}v_a$. As it is given that the degree of $v_a$ is even ,then $v_a$ ...
0
votes
1answer
33 views

What is Graph Isomorphism and Graph Invariant?

While I was reading Reinhard Diestel text on graphs, I came across this paragraph. Let G = (V, E) and G' = (V' , E' ) be two graphs. We call G and G' isomorphic,and write G $\simeq $ G' , if ...
5
votes
2answers
102 views

Domino Trains Questions

A train is an end-to-end arrangement of dominoes such that the adjoining halves of neighboring dominoes have the same number of dots. A "double-$n$'' domino set has one of each possible domino using ...
3
votes
1answer
40 views

cycle space in graph theory

I read the following definition of the cycle space in a set of notes. Definition (Cycle space): Let $G=(V,E)$ . The cycle space of $G$ is an element of $2^{E}$ denoted $\mathcal{C}$ and is the ...
4
votes
0answers
37 views

Graph vertex set with a certain property

Let $G$ be a graph and let $V$ be a set of vertices with the following property: If a vertex $v$ is connected to every $u\in V$, then $v$ has to be in $V$. Does such $V$ have a (standard) name? Note ...
3
votes
1answer
27 views

Every other vertex shares $5$ neighbors with fixed vertex

An undirected graph has $30$ vertices; one of them is $v$. Each vertex $w\neq v$ shares exactly $5$ neighbors with $v$. Is it true that some vertex must have odd degree? We could try counting the ...
1
vote
2answers
67 views

Given a directed graph, give an adjacency list representation of the graph that leads BFS to find the following spanning tree

Given a directed graph: give an adjacency list representation of the graph that leads Breadth first search to find the spanning tree in the left below. And give an adjacency list representation ...
1
vote
3answers
45 views

When is a graph balanced bipartite?

I have a quick question: is there any sufficient condition (theorem, lemma, proposition,...) to show that a graph (vertices do not have the same degree) is balanced bipartite?
0
votes
1answer
83 views

Prove that a tree in which every vertex has degree at most 2 is a simple path

Prove that a tree in which every vertex has degree at most 2 is a simple path. More precisely: Let $G = (V,E)$ be an undirected tree, with $|V| = n \geq 1$ and assume that every vertex has degree ...
2
votes
1answer
35 views

Minimum cost edge, Minimum Spanning Tree — Graph

Please could I ask for some help with this exam past paper question: A connected graph G has five vertices and has eight edges with lengths 8, 10, 10, 11, 13, 17, 17 and 18. (a) Find the minimum ...
1
vote
0answers
21 views

Graph Relatives for Tessellation of the Hyperbolic Plane

I'm trying to get into the theory about the Moduar group. Among the "Paracompact hyperbolic uniform tilings in [∞,3] family" in the section "Tessellation of the hyperbolic plane" I found the Order-3 ...
1
vote
1answer
30 views

What are the cycles in this graph, and what are their sizes?

I have the following graph $G$. I'd like to find how many cycles there are and what their sizes are. Please correct me if I am wrong: in this graph there are $2$ cycles, $\text{1-2-3-4-5-1}$ with ...
4
votes
2answers
13 views

Prove that the path between two nodes is unique if the graph is a tree.

I think that the proof is easy assuming that there are at least two paths between any two nodes. If that is true then there must be a cycle somewhere. But if there is a cycle then this is not a tree, ...
0
votes
1answer
25 views

Good resources on chemical graph theory

Are there some good resources on chemical graph theory, mainly some covering even the recent results (past 2000)? Tnaks in advance for any help.
1
vote
1answer
41 views

Proving that between each pair of vertices there is a path length $2$ at most

Let $G=(V,E)$ be a graph with $n$ vertices such that $\forall v,w\in V$ that doesn't have a common edge we have: $\text{deg}(v)+\text{deg}(w)\ge n-1$. Prove that for each pair of vertices ...
1
vote
2answers
38 views

How many trees does a forest with n vertices and m edges contain?

Concerning trees in graph theory: How many trees does a forest with $n$ vertices and $m$ edges contain? This has to do with combinatorics apparently but I'm struggling with these assignments ...