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

2
votes
1answer
49 views

Graph theory : the adjacency matrix of an n-dimensional torus

Is there, in principle, an easy way to determine the adjacency matrix of an n-dimensional torus that's only connected to neighbours which it shares a corner/edge/face/volume/etc with (n>1 obviously; ...
1
vote
2answers
26 views

Number of edges Upper Bound

Given a simple graph with $n$ vertices and $m$ edges, then show: $m \le \binom{n}{2}$. Obviously the equality holds when the graph is complete, and if you have less edges, then the inequality would ...
1
vote
2answers
71 views

Algorithm for finding graph levels

I have found an algorithm to separate a graph in its different levels, but as I don't know its name, and I couldn't find it anywhere else I don't trust it 100%. It goes like this: ...
0
votes
0answers
27 views

Name of a vertex set of the same out-degree

I have a graph and it is very important to me to distinguish vertex sets of the same out-degree. For example, I have a set of all vertex of the out-degree 1, a set of all vertex of out-degree2, and so ...
3
votes
1answer
49 views

classify all surface in which $K_{3,3}$ and $K_5$ can be embedded.

Using the fact that $K_{3,3}$ and $K_5$ are not planar, classify all surface in which $K_{3,3}$ and $K_5$ can be embedded. I know $K_5$ can be embedded into a torus. Can anyone give a hint for the ...
-1
votes
0answers
161 views

need mathematical expression for the below [closed]

Want to convert below algorithm into a mathematical model:- General points 1. Let there be a Connected Directed Graph. G = (V, E) V vertices or nodes E edges. This graph can be seen as a network ...
1
vote
1answer
36 views

Find the number of vertices that belong to all the maximum matchings of a general connected graph .

The given graph is connected but not necessarily bipartite. Please describe the complete approach with useful links , I read stuff related to augmenting paths but could not comprehend well. An O(VE) ...
0
votes
1answer
30 views

Graph Theory : Strongly regular graph

A simple graph G which is neither empty nor complete is said to be strongly regular with parameters $(v,k,λ,μ)$ if: v(G)=v; G is k-regular; any two adjacent vertices of G have λ common neighbours, ...
0
votes
1answer
18 views
0
votes
1answer
22 views

How-many-different-adjacency-matrix-with-N-vertices-and-E-edges-have?

i'm studing graphs in algorithm and complexity and was perplexed in front of the following questions. I hope I get clear explanation for it... ...
3
votes
2answers
153 views

IMO 1995 Shortlist problem C5

IMO 1995 Shortlist problem C5 At a meeting of $12k$ people, each person exchanged greetings with exactly $3k+6$ people. For any two people, the number who exchange greetings with both is ...
0
votes
0answers
26 views

sum of minimal cuts in a cut space

I'm reading about the cut space of a graph and I was wondering how I could show that given two sets of minimal cuts which share some common edges such that their sum modulo 2 also forms a minimal cut ...
29
votes
1answer
2k views

Is Wolfram wrong about unique 3-colorability, or am I just confused?

The illustration on Wolfram's page claims to present a uniquely colorable, triangle-free graph. However, this seems to be blatantly false: the graph has a symmetry with respect to a reflection through ...
4
votes
2answers
47 views

Prove that $x\ge n(n-1)(n-3)/8$, where $x$ is the number of $C_4$ cycles in a graph.

If there are no $C_4$ cycles in a graph the edges in $G$, ie, $e(G)\le\frac n4(\sqrt{4n-3}+1)$, but if $e(G)\ge\frac12 {n \choose 2}$, we have to show that $x$ (number of $c_4$ cycles) $\ge ...
1
vote
1answer
32 views

how to define a “directed spanning tree”?

In all my books and articles about "graph theory", I didn't find the definition of "directed spanning tree". Could you please give this definition and the reference? How to judge if a directed graph ...
0
votes
1answer
48 views

How can I make graphs in matlab?

for my thesis I have to include figures. I want to make a figure as the figure in the attachment, but since I am pretty new to matlab I do not understand the best way (I know this may be a many ...
1
vote
1answer
45 views

Graph theory - how to find nodes reachable from the given node under certain cost

I'm considering the following problem (very rough description): Assume we have a graph where edges are assigned some non-negative costs, a starting node s and some ...
0
votes
1answer
36 views

size of an independent set of any graph with $n$ vertices and maximum degree $d$

I have to show that any graph with $n$ vertices and maximum degreee $d$ contains an independent set of size at least $\frac{n}{d+1}$. Why $d+1$? Can you please help me or give me a hint? Thanks a lot! ...
1
vote
0answers
15 views

Size of intersection of balls on non-ameanable graphs

Let $G$ be a vertex-transitive non-ameanable graph and let $B(x,n)$ be the ball of radius $n$ centered on the vertex $x$. I am interested in estimates on the cardinality of the following set, ...
1
vote
0answers
42 views

How to mathematically judge if there is a spanning tree in a graph?

Given a graph $G=(V,E,A)$ where $V$ is the set of the vertices, and $E$ is the set of sides, and $A$ is the adjacency matrix of dimension $n\times n$. $G$ is undirected or directed. We define the ...
0
votes
0answers
38 views

Confused about Graph Theory Language

I was confused about some of the wording in this definition I came upon: Let G be a control flow graph (a control flow graph you can imagine as a directed graph) for program P. A hammock H is an ...
1
vote
1answer
20 views

Every graph G with at least one edge has a subgraph H with $\delta(H) > \varepsilon(H) \geqslant \varepsilon(G)$

I would like to know how to proof (or any other alternative proof) and understanding the intuition of this proposition, it it taken from textbook "Graph Theory" by Reinhard Diestel, P.5 Proposition ...
0
votes
2answers
21 views

A finite graph G has an even number of vertices with odd valency.

Theorem: A finite graph G has an even number of vertices with odd valency. Now, I draw a finite graph : The number of vertices is 4. And Degree(1) = 1, Degree(2) = 2, Degree(3) = 2, Degree(4) = 1. ...
1
vote
1answer
32 views

How to get value of this binomial coefficient expression?

I am trying to work out an upper bound (big O) of an algorithm I thought of in graph theory field. Basically I have a graph $G=(V,E)$. And a subset of vertices $A=\{a_1,a_2,...,a_k\} ∈ V$ such that ...
3
votes
0answers
11 views

how to have the highest increase in eigenvelue of an adjacecny matrix adding a single arc?

Let's suppose I have a generic directed graph $G$ and it's adjacency matrix $A$. I can add an arc wherever I want in the graph. (i.e. perturb the matrix A changing a single 0 into a 1). Where should ...
0
votes
1answer
25 views

treewidth and a complete k-vertex Subgraph

the question I'm concerned with is twofold. First: I'm wondering about the relationship between complete subgraphs and $k$-degeneracy. Let $G$ be an undirected simple graph. A regular subgraph of ...
0
votes
0answers
50 views

Why finding chromatic number is NP-Hard?

We know that the chromatic number of a graph $G$ is the smallest number of colors needed to color the vertices of $G$ so that no two adjacent vertices share the same color . But why the coloring is ...
3
votes
1answer
51 views

Dependency of submatrix used in a combinatorial strategy .

This is a verification post , Please inform if anything is undefined or unclear or miss-tagged. Also if you vote up/down it would be helpfull if you leave a comment. Introduction: Given a matrix A ...
1
vote
0answers
16 views

All possible depth first spanning trees of a directed graph.

I am looking for an algorithm that generates all possible depth first spanning trees of a directed graph that has a known root.
2
votes
0answers
31 views

What is the difference between a lower bound and an upper bound in an Interval Graph $G(I)$

As I know that the maximal size of an independent set $IS$ of an interval Graph $G$ is a lower bound. Now what is exactly the upper bound, and when they might be equivalent to each other. are there ...
1
vote
0answers
38 views

Number of connected components of an induced subgraph

Given a graph ($V$,$E$) with $n$ vertices and $m$ edges. Suppose it has $l$ connected components, labeled by $1,2,\dots,l$, with sizes $a_1,a_2,\dots,a_l$ respectively. Now we arbitrarily pick $k$ out ...
3
votes
0answers
72 views

Graph theory, $n$ people sitting around table.

$n$ people want to have dinner together around a table for $k$ nights so that no person has the same neighbor twice. How big can $k$ be in terms of $n$? Does everybody get to sit next to everybody ...
2
votes
1answer
50 views

Doubt about claim about complexity of edge coloring powers of the line graph

Likely I am misunderstanding/missing something, but a claim in a paper appears wrong to me. According to Coloring Graph Powers: Graph Product Bounds and Hardness of Approximation p. 2 Unless ...
1
vote
0answers
28 views

largest distance between vertices on a polyhedron

I have a polyhedron defined by m inequations and n unknowns. I am interested in the largest distance between two vertices (the number of edges I have to follow from one vertex to another). I am ...
1
vote
1answer
189 views

Balancing the weights of the vertices of a graph by averaging along the edges.

Suppose that you have a graph, and someone assigned real numbers to every vertex. You can modify these numbers by replacing the numbers on two adjacent vertices by their average. Your goal is to reach ...
4
votes
1answer
82 views

Algorithm to find shortest path to net values across nodes

I have an undirected graph $G = (V, E)$ with nodes $V$ and edges $E$. Each node $v$ has an associated number $n_v \in \mathbf{Z}$ Let us define for any two nodes $v, w \in V$ connected by an edge $e ...
6
votes
0answers
59 views

Given $100$ coplanar points, no $3$ collinear, then at most $70$ percent triangles formed using these points are acute-angled

(IMO-$1970$) Given $100$ coplanar points, no $3$ collinear, prove that at most $70$ percent of the triangles formed using these points are acute-angled. I know that one solution proceeds by ...
1
vote
0answers
13 views

Adam isomorphism of circulant graphs

Let $C(n; S)$ denote a circulant graph on $n$ vertices (the vertices can be labeled $0,\ldots,n-1$), and connection set $S = \{s_1, \ldots, s_k \}$. Let $1 \leq \mu < n$ be relatively prime to $n$. ...
1
vote
2answers
34 views

A graph with $V$ vertices has at most $V(V-1)/2$ Edges

I am reading about graph theory. A graph with $V$ vertices has at most $V(V-1)/2$ Edges Proof: The total of $V^2$ possible pairs of vertices include $V$ self-loops and accounts twice for each edge ...
3
votes
0answers
27 views

Number of spanning trees in $K_n -e$ [duplicate]

Let $K_n$ a complete graph on $n$ vertices, and let $e$ be an edge of $K_n$. I want to find the number of spanning trees in $K_n-e$. Here is my attempt: I use two theorems: Theorem 1. Let $\tau(G)$ ...
1
vote
1answer
30 views

4-Color Theorem question - is the set of 4-vertex-colorings of a planar graph closed under Kempe switching?

A $4$-vertex-colored planar graph $G$ is a planar graph $G \overset{\text{def}}{=} (V, E, C)$ where $V$ and $E$ are as usual and $C$ consists of pairs $(v \in V, c \in \{1,\dots,4\})$ such that ...
1
vote
0answers
25 views

Number of same degree vertex pairs between two random graphs

I am considering the random graphs generated by the Erdős-Rényi model for this question. Random Graphs as Models of Networks by Newman is a reference on this topic. A random graph $\Gamma_{n,p}$ has ...
3
votes
1answer
43 views

Prove that the graph dual to Eulerian planar graph is bipartite.

How would I go about doing this proof I am not very knowledgeable about graph theory I know the definitions of planar and bipartite and dual but how do you make these connection
3
votes
1answer
43 views

Calulating the Ramsey number $R(T, K_{1,n})$ of a tree $T$ and bipartite graph $K_{1,n}$

Let $m,n \ge 2$ be such that $m-1$ is a divisor of $n-1$. Let $T$ be a tree with $m$ vertices. Calculate the Ramsey number $R(T,K_{1,n})$. Thoughts: I'm having trouble approaching this question. ...
1
vote
1answer
31 views

maximal matching in graph theory

if we have a graph $G = (V,E)$ and the four values $\beta_1(G)$, $\alpha_1(G)$, $\beta(G)$, $\alpha(G)$, where $\beta_1(G)$: Edge independenth number. The maximal number of independent edges in the ...
5
votes
1answer
57 views

Open Questions on Latin Squares and Directed Acyclic Graphs

Every Latin square corresponds to a directed acyclic graph (DAG) with a lattice arrangement, and whose $2N(N-1)$ edges indicate label order (<). For example: ...
-2
votes
1answer
14 views

Central vertex of a cyclic graph and of a complete graph [closed]

What is the central vertex for a cyclic graph $C_n$? and for complete graph $K_n$? The eccentricity is the same for all vertices!
0
votes
1answer
43 views

Proof that any connected Graph has at least $n-1$ edges

I would really appreciate if someone could check this proof i though. Bare in mind i learned this subject in another language so i apologize in advance for my english. By Induction: $G$ connected ...
0
votes
1answer
22 views

Counting weakly connected graphs with outdegree of exactly one.

If we count all graphs of $N$ labelled vertices, where each vertex has an outdegree of exactly $1$ with no self-loops allowed, we'll find that there are exactly $(N-1)^N$ of them (for every of $N$ ...
6
votes
0answers
63 views

Does there exist a graph $G$ such that every edge is contained in a unique Hamiltonian circuit, that is not a cycle graph?

Suppose $G$ is an (undirected, simple) finite graph. If $G$ is a cycle graph, then each edge of $G$ belongs to a unique Hamiltonian circuit. Does there exist a non-cycle graph $G$ with this property?