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

1
vote
0answers
5 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.
1
vote
0answers
11 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
25 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 ...
2
votes
0answers
54 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
36 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
21 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
0answers
33 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
0answers
66 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
41 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 ...
0
votes
0answers
9 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
32 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
25 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
27 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
21 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
38 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
24 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
29 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 ...
4
votes
1answer
39 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
13 views

Central vertex of a cyclic graph and of a complete graph [on hold]

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!
-1
votes
1answer
30 views

Prove that, in a simple graph G with n vertices and a edges, $2a \le n^2-n$ [on hold]

Prove that, in a simple graph G with $n$ vertices and $a$ edges, $2a \le n^2-n$.
0
votes
1answer
42 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
20 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$ ...
5
votes
0answers
42 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?
0
votes
0answers
29 views

Piecewise Logistic Function [Satellite Data] [on hold]

I am working with $16$-day MODIS EVI (satellite) data and I want to fit a Piece-wise Logistic Function through my $23$ EVI data values. The following formula is for the Piece-wise Logistic Function: ...
2
votes
1answer
27 views

Is there a special name for graphs that have “check board” property?

Is there a special name for a graph, all vertices of which can be divined into two sets in such a way, that any edge connects vertices of different sets?
0
votes
0answers
16 views

Self-complementary graph and cut-vertices

Statement: A self-complementary graph has a cut-vertex if and only if it has a vertex of degree 1. It is true that if $v$ is a cut-vertex, then at least there are two components that when one ...
0
votes
0answers
37 views

Notion of degree for infinite graphs?

If you are studying graphs with vertices in the real numbers, you can define a notion of degree for a vertex as the length of the set of vertices directly connected to that vertex (if you wanted, you ...
1
vote
2answers
27 views

Proof that if a simple Graph contains at most two nodes with odd degree then it has a Euler walk

My proof would be start as the following : In general if there are two node at most, then one node used to start walking and the other to end. A) If we start from odd one, this means we have two ...
3
votes
0answers
23 views

Finding binary operations on connected graphs

If $G = (V,E)$ is a connected graph with $||V|| \geq 2$ , $W(G)$ being the set of all paths in $G$. How do you find a binary operation $ +$ on $W(G)$ such that $\langle W(G),+\rangle$ is an algebra ...
1
vote
1answer
17 views

Cliques in $k$-partite graphs

Recall that a $k$-partite graph is a graph whose vertices are or can be partitioned into k different independent sets and that a clique of a graph is subset of the vertices such that every two ...
0
votes
2answers
27 views

Show that the sum of (outdeg(v)-indeg(v))=0

Let $G = (V,E,\Phi)$ a directed graph. Let $outdeg(v)=\#\{e \in E| source(e) = v\}$ and $indeg(v)=\#\{e \in E| sink(e) = v\}$. Show that $$\sum \limits_{v \in V}(outdeg(v)-indeg(v)) = 0$$ Can you ...
2
votes
1answer
38 views

Puzzle: Determining the structure of a bipartite graph

Consider the bipartite graph $G = (X, Y, E)$, with $|X| = |Y| = n$. We can think of $X$ and $Y$ as clusters of $n$ switches on either end of a long hallway. Each switch on one end of the hallway has ...
0
votes
1answer
16 views

Find longest route through graph with restrictions

Q.4 from http://www.iarcs.org.in/inoi/2015/zio2015/zio2015-question-paper.pdf All flights must originate at airport 0 and end at airport 2. The types of flight taken during the sequence must match ...
1
vote
2answers
38 views

Prove that in a simple graph with $\geq 2$ nodes at least one node can be removed without disconnecting the graph

Prove that in any simple graph $G$ with number of nodes $\geq 2$ there is at least one node $v$ that can be removed with its all edges, and keep the graph connected? From my point of view I can say ...
1
vote
0answers
24 views

What is the formalism for a map that returns the adjacent vertex positions of a given adjacency matrix?

How do I formally denote a map that returns the adjacent vertex positions of a given adjacency matrix? Example: V = undirected adjacency matrix $$ V = \left[ \begin{matrix} v_{1,1} & v_{1,2} ...
0
votes
0answers
42 views

Hall's theorem proof - capacity of middle edges

The Hall's theorem say that for un-directed bipartite graph $G=(U,W,E)$ and $$|U|=|W|=n,$$ there is a prefect matching if and only if for every subset $X$ of $U$, $$|X|\le |N(X)|.$$ I read the ...
0
votes
0answers
66 views

Number of graphs with 5 vertices

Let $v_i$ where $i=1,2,3,4,5$ be vertices of a graph. Each vertex makes only one directed edge to any other vertex. For instance $v_1 \to v_2 \to v_3 \to v_4 \to v_5 \to v_1$ and $v_1 \to v_3 \to v_4 ...
5
votes
1answer
108 views

How can I calculate the formula of this fractal-like structure?

I did the following fractal-like structure manually, and I was trying to convert it to a formula (or an algorithm including formulas) to compute some parts of the drawing, but I get lost due to the ...
2
votes
1answer
35 views

Let G be a simple graph with n vertices and m edges. Prove the following holds!!

Let G be a simple graph with n vertices and m edges. Prove the following holds using the Handshake Theorem: $$\frac{m}{\Delta} \leq \frac{n}{2} \leq \frac{m}{\delta}$$ where: $\Delta$ is the maximum ...
1
vote
0answers
44 views

How to give a rigorous proof of a fact about convex polygon?

I claim that there exists universal constants $0<\delta_1(m), \delta_2(m)<1$ such that for any convex polygon $P$ in $\mathbb{R}^n$ with $m$ faces, \begin{equation} \frac{\mathcal{H}^{n-1}(\{x ...
2
votes
1answer
28 views

Counterexample to a variation on “The politician theorem”.

The following is a theorem in graph theory that has a nice 'real world' interpretation: Suppose $G$ is a finite simple graph in which any two vertices have precisely one common neighbour. Then ...
0
votes
0answers
20 views

graph theory k -coloring proofs, specific problem using countries and neighbors

prove that if any country has at least 5 neighbors, then there are two neighboring countries such that there are not more than 9 other countries adjacent to at least one of these two, each country is ...
1
vote
0answers
21 views

Graph Theory, West, 2nd ed, Exercise 1.2.14

The claim to prove, or disprove is as follows: The union of the edge sets of distinct $u,v$-paths must contain a cycle. The proposed solution is the following: Proof (extremality): Let $P$ ...
0
votes
1answer
22 views

Is every bijective pseudograph homomorphism a pseudograph isomorphism?

The term pseudograph describes a graph that may have parallel edges and loops. Formally this is a triple $G = (V,E,\delta)$ with $V,E$ sets and a map $\delta \colon E \to (V \times V)/\sim$, where ...
4
votes
1answer
32 views

Proposition $1.3$ in Bondy & Murty's Graph Theory.

Let $G[X,Y]$ be a bipartite graph, with no isolated vertices, and $d(x) \ge d(y)$, $\forall$ $xy \in E$ (where $E$ denotes the set of edges in $G$). Then: $|X| \le |Y|$, with equality iff $d(x) = ...
0
votes
0answers
18 views

Standard notation for the set of children of a node in a rooted tree

In graph theory, given a rooted tree $T$ and a node $a \in V(T)$, is there a standard way to refer to the set of all children of $a$? I have seen $CHILDREN_T(a)$ being used, but this seem quite clumsy ...
2
votes
1answer
45 views

Friendship theorem: need help with part of proof.

Suppose $G$ is a simple graph such that every two of its vertices have exactly one common neighbor. The friendship theorem says that $G$ must be a friendship graph (a bunch of triangles joined at a ...
0
votes
0answers
22 views

Determine $ex(n,P_k)$ for each pair of n and k

I have to find the maximum number of edges in $P_k$ free graph where $P_k$ is path of length $k$. I know the result that a graph on $n$ vertices with no path of length $k$ has edges$\ \le ...
1
vote
0answers
22 views

Maximum number of edges in a subgraph of hypercube

Let $H_n$ is an $n$-dimensional hypercube, $|V(H_n)|=2^n, |E(H_n)|=n2^{n-1}$. Let $M\subset V(H_n), |M|=2^k, 1\le k<n$, and $G_M$ is a subgraph of $H_n$ induced by $M$, $V(G_M)=2^k$. Prove that ...
0
votes
2answers
24 views

$K_n$ as an union of bipartite graphs

Theorem: The complete graph $K_n$ can be expressed as the union of $k$ bipartite graphs if and only if $n \leq 2^k.$ I would appreciate a pedagogical explanation of the theorem. Graph Theory by West ...