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
0answers
20 views

Number of spanning trees in $K_n -e$

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)$ ...
0
votes
0answers
12 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
12 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 ...
2
votes
1answer
29 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
17 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
26 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 ...
1
vote
0answers
21 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
28 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
37 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
18 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
38 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
24 views

Piecewise Logistic Function [Satellite Data]

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
25 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
24 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
25 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
35 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
15 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
23 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
41 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
64 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 ...
3
votes
0answers
58 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
32 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
21 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
31 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
17 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
19 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 ...
1
vote
1answer
16 views

Showing an outerplaner graph has less than $2n-3$ edges

An outerplanar graph is a connected plane graph that can be drawn in such a way that all it's vertices are on the outer face. I want to show that for every $G$ outerplaner graph with $n$ vertices and ...
4
votes
2answers
47 views

(A question regarding:) the graph associated with an open cover of a topological space.

Let $X$ denote a topological space and suppose that $\mathcal{O}$ is an open cover of $X$. Assume $\emptyset \notin \mathcal{O}.$ (Thanks Niels!) Now make $\mathcal{O}$ into an (undirected) graph as ...
2
votes
1answer
46 views

Homology of a graph.

Let $\Gamma$ be a graph with $V$ vertices and $E$ edges. If we orient the edges, we can form the incidence matrix of the graph. This is a $V\times E$ matrix whose $(i j)$ entry is $+1$ if the edge ...
0
votes
0answers
18 views

It is possible to have multiple values in one graph node

Look at the graph: I have this graph and i want to return all possible groups of the graph. Each group is a node, or all the nodes directly below that node. So we can have this type of groups: ...
-3
votes
1answer
25 views

Determine the number of graphs with v vertices [closed]

How can one determine the number of graphs with a certain number of vertices?
10
votes
2answers
585 views

In a graph, can an edge be in less than 2 faces?

In the proof that for every conective plane graph on $n$ vertices and $m$ edges $m\leq 3(n-2)$ I encountered the statement: $\Sigma_{f\in F} f\leq 2m$, and the explanation was that every edge is in at ...
2
votes
3answers
23 views

Picking edges from a connected graph so that any vertex is incident with an odd number of those edges

Suppose you are given a connected graph G having an even number of vertices. Show that you can select a set $E$ of edges from this graph so that any vertex in G is incident with exactly an odd ...
1
vote
1answer
30 views

Graph and tree computation

A graph is given with set of nodes $[x_1,x_2,x_3,\ldots,x_6]$ and with set of edges: $$\{[x_1,x_2], [x_1,x_3], [x_1,x_4], [x_1,x_5], [x_1,x_6], [x_2,x_3], [x_2,x_6], [x_3,x_4], [x_4,x_5], ...
-1
votes
2answers
24 views

What is the adjacency matrix and number of paths of length $4$ between vertex $2$ and vertex $5$ in the null graph on $\{1,2,3,4,5\}$? [closed]

Given the following graph 1) Compute adjacency matrix 2) Compute the number of paths of length 4 from knot Nr.2 to knot Nr.5 Can anyone provide a solution how to do it?
6
votes
1answer
38 views

$2$-coloring of graph has large connected subgraph with one color

Given a graph $G$ with $n$ vertices. Let $k$ denote the minimum degree among the vertices. Suppose that $k\geq 3n/4$. We color the edges of $G$ in $2$ colors. Prove that there is a connected subgraph ...
1
vote
1answer
28 views

Definition of Reducible matrix and relation with not strongly connected digraph

I connot quite understand the definition of reducible matrix here. We know $A_{n\times n}$ is reducible, when there exists a permutation matrix $\textbf{P}$ such that: $$P^TAP=\begin{bmatrix}X ...